Arindam Khan Defense Dissertation

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 a 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 have implications in many other related problems.