*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
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.
