Arindam Khan Defense Dissertation

Monday, August 10, 2015 - 11:00am
Title: Approximation Algorithms for Multidimensional Bin Packing
Advisor: Dr. Prasad Tetali, School of Mathematics
Committee: Dr. Prasad Tetali, School of Mathematics
  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

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.