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

Location: Klaus 2100

Title : Approximation Algorithms for Multidimensional Bin Packing.

Arindam Khan

PhD Candidate in Algorithms, Combinatorics, and Optimization School of Computer Science Georgia Institute of Technology akhan67@gatech.edu http://www.cc.gatech.edu/~akhan67/

Committee:

Dr. Prasad Tetali (Advisor), School of Mathematics and School of Computer Science 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

Reader:

Dr. Nikhil Bansal, TU Eindhoven, Netherlands.

The thesis is available for public inspection in the School of Mathematics lounge (Skiles 236), the ARC lounge (Klaus 2222), the ISyE PhD student lounge, and at the URL http://www.aco.gatech.edu/sites/default/files/documents/khan_thesis.pdf

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.