Approximation algorithms for multidimensional bin packing

摘要

The bin packing problem has been the corner stone of approximation algorithms and has been extensively studied starting from the early seventies. \nIn the classical bin packing problem, we are given a list of real numbers in the range (0, 1], the goal is to place them in a minimum number of bins so that no bin holds numbers summing to more than 1.\nIn this thesis we study approximation algorithms for three generalizations of bin packing: geometric bin packing, vector bin packing and weighted bipartite edge coloring.\n\nIn two-dimensional (2-D) geometric bin packing, 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.\nWe consider the widely studied orthogonal packing case, where the items must be placed in the bin such that their sides are parallel to the sides of the bin. \nHere two variants are usually studied, (i) where the items cannot be rotated, and (ii) they can be rotated by 90 degrees. We give a polynomial time algorithm with an asymptotic approximation ratio of\n$\\ln(1.5) + 1 \\approx 1.405$ for the versions with and without rotations.\nWe have also shown the limitations of rounding based algorithms, ubiquitous in bin packing algorithms. We have shown that any algorithm that\nrounds at least one side of each large item to some number in a constant size collection values chosen independent of the problem instance, cannot achieve an asymptotic approximation ratio better than 3/2. \n\nIn d-dimensional vector bin packing (VBP), each item is a d-dimensional vector that needs to be packed into unit vector bins. The problem is of great significance in resource constrained scheduling and also appears in recent virtual machine placement in cloud computing. Even in two dimensions, it has novel applications in layout design, logistics, loading and scheduling problems. \nWe obtain a polynomial time algorithm with an asymptotic approximation ratio of $\\ln(1.5) + 1 \\approx 1.405$ for 2-D VBP. We also obtain a polynomial time algorithm with almost tight (absolute) approximation ratio of $1+\\ln(1.5)$ for 2-D VBP.\nFor $d$ dimensions, we give a polynomial time algorithm with an asymptotic approximation ratio of $\\ln(d/2) + 1.5 \\approx \\ln d+0.81$. \nWe also consider vector bin packing under resource augmentation. We give a polynomial time algorithm that packs vectors into $(1+\\epsilon)Opt$ bins when we allow augmentation in (d - 1) dimensions and $Opt$ is the minimum number of bins needed to pack the vectors into (1,1) bins.\n\nIn weighted bipartite edge coloring problem, we are given an edge-weighted bipartite graph $G=(V,E)$ with weights $w: E \\rightarrow [0,1]$. The task is to find a proper weighted coloring of the edges with as few colors as possible. An edge coloring of the weighted graph is called a proper weighted coloring if 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 very useful in various applications in interconnected networks and routing. \nWe show a polynomial time approximation algorithm that returns a proper weighted coloring with at most $\\lceil 2.2223m \\rceil$ colors where $m$ is the minimum number of unit sized bins needed to pack the weight of all edges incident at any vertex. \nWe also show that if all edge weights are $>1/4$ then $\\lceil 2.2m \\rceil$ colors are sufficient.