# Phd Defense by Arindam Khan

Event Details
• Date/Time:
• Monday August 10, 2015
11:00 am - 1:00 pm
• Location: Klaus 2100
• Phone:
• URL:
• Email:
• Fee(s):
N/A
• Extras:
Contact
No contact information submitted.
Summaries

Summary Sentence: Approximation Algorithms for Multidimensional bin packing

Full Summary: No summary paragraph submitted.

Final doctoral examination and defense of dissertation of Arindam Khan

Title : Approximation Algorithms for Multidimensional bin packing

Time: Monday, August 10th, 11:00am

Location: Klaus 2100

Dr. Prasad Tetali, School of Mathematics and School of Computer Science

Committee:

Dr. Santanu Dey, School of Industrial and Systems Engineering Dr. Sebastian Pokutta, School of Industrial and Systems Engineering Dr. Dana Randall, School of Computer Science Dr. Santosh Vempala, School of Computer Science

Dr. Nikhil Bansal, TU Eindhoven

Abstract:

The bin packing problem is a classical NP-hard problem. In this thesis we study approximation algorithms for three generalizations of bin packing: geometric bin packing (GP), vector bin packing (VP) and weighted bipartite edge coloring (WC).

In two-dimensional (2-D) GP, we are given a collection of rectangular items to be packed into a minimum number of unit-size square bins.  Geometric packing has vast applications in cutting stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related problems. We give a polynomial time algorithm with an asymptotic approximation ratio of (1+ ln(1.5)) < 1.406.

In d-dimensional VP, each item is a d-dimensional vector that needs to be packed into unit vector bins.  Consider the bins as servers with d different resources (CPU, memory, bandwidth etc.) and each item as a job requiring some specified amount of each resource, then the problem corresponds to scheduling jobs feasibly on minimum number of servers.  Even in 2-D, it has novel applications in layout design, logistics and virtual machine placement in cloud computing. For the 2-D case we give an asymptotic approximation guarantee of (1+ ln(1.5) < 1.406 and tight 1.5 absolute approximation guarantee. For the d-dimensional case, we get a (0.807+ln d) guarantee.

In WC, we are given an edge-weighted bipartite graph. The task is to find a weighted coloring of the edges with as few colors as possible such that the sum of the weights of the edges incident to a vertex of any color is at most one. This problem is motivated by rearrangeability of 3-stage Clos networks which is extremely useful in interconnected networks and routing.  We obtain a polynomial time 20/9 approximation algorithm.

One of our key technical contribution is to extend a randomized rounding based method to constant rounding based algorithms, ubiquitous in bin packing. This might have implications in many other related problems.

In Campus Calendar
No
Groups