New results for several bin packing and related problems
MetadataShow full item record
Bin packing is a fundamental problem in theoretical computer science, especially in combinatorial optimization, and has been extensively studied in the past. A long and rich history exists for this problem, and many important results have been obtained. Due to its wide applications in various applied areas, a number of variants of this problem have been investigated and new variants are repeatedly introduced. In this dissertation, we study several new variants of the classical bin packing problem. The first variant we study is a bin coloring problem first introduced in . For this variant, we consider two problems called Minimum Bin Coloring Problem (MinBC) and Online Maximum Bin Coloring Problem (OMaxBC). In both problems, we need to pack a set of unit-sized items with each associating a color into a set of bins with capacity B. For MinBC, the objective is to minimize the maximum number of different colors in each bin, while for OMaxBC, the objective is to maximize the minimum number of different colors in each bin. For the APX-hard MinBC problem, we present two near linear time approximation algorithms to achieve almost optimal solutions, i.e., no more than OPT + 2 and OPT + 1 respectively, where OPT is the optimal solution. For the OMaxBC problem, we first introduce a deterministic 2-competitive greedy algorithm, and then give lower bounds for any deterministic and randomized (against adaptive offline adversary) online algorithms. The lower bounds show that our deterministic algorithm achieves the best possible competitive ratio. The second variant we consider is called Maximum Resource Bin Packing (MRBP), first studied in . In this variant, bins are ordered so that no item in a later bin fits in any earlier bin, and the objective is to maximize the total number of packed bins. The best previous result on this problem is a [Special characters omitted.] <math> <f> <fr><nu>6</nu><de>5</de></fr></f> </math> -approximation achieved by a First-Fit-Increasing (FFI) algorithm. In this dissertation, we present a new algorithm following the spirit of First-Fit-Increasing with an asymptotic approximation ratio of [Special characters omitted.] <math> <f> <fr><nu>80</nu><de>71</de></fr></f> </math> [approximate] 1.12676. We then study a generalized version of the MRBP problem, called the Cardinality Constrained MRBP (CCMRBP) problem, in which each bin is only allowed to contain at most C items, and show that CCMRBP is no harder to approximate than MRBP. At last, we further generalize MRBP to two dimensions and presents an approximation algorithm with asymptotic ratio in [[Special characters omitted.] <math> <f> <fr><nu>13</nu><de>6</de></fr>,<fr><nu>12</nu><de>5</de></fr> </f> </math> ]. The third variant we investigate is a lazy bin covering problem which minimizes the total number of used bins in such a way that no item can be removed from a covered bin without making it uncovered. For this variant, we consider its both online and offline versions. For the offline version, we first analyze the approximation ratios of a number traditional packing strategies for this problem and its parameterized version, and finally present a near linear time [Special characters omitted.] <math> <f> <fr><nu>17</nu><de>15</de></fr></f> </math> -approximation algorithm and an APTAS. For the online version, we give competitive analyses for a number traditional packing algorithms, such as Next-Fit, Worst-Fit, First-Fit, and a new HARMONIC M algorithm.