Approximation Schemes for Ordered Vector Packing Problems Export

@incollection{citeulike:2385695, abstract = {In this paper we deal with the d-dimensional vector packing problem, which is a generalization of the classical bin packing problem in which each item has d distinct weights and each bin has d corresponding capacities. We address the case in which the vectors of weights associated with the items are totally ordered, i.e., given any two weight vectors a i, a j, either a i is componentwise not smaller than a j or a j is componentwise not smaller than a i, and construct an asymptotic polynomial-time approximation scheme for this case. As a corollary, we also obtain such a scheme for the bin packing problem with cardinality constraint, whose existence was an open question to the best of our knowledge. We also extend the result to instances with constant Dilworth number, i.e. instances where the set of items can be partitioned into a constant number of totally ordered subsets. We use ideas from classical and recent approximation schemes for related problems, as well as a nontrivial procedure to round an LP solution associated with the packing of the small items.}, author = {Caprara, Alberto and Kellerer, Hans and Pferschy, Ulrich}, citeulike-article-id = {2385695}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/3-540-44666-4_11}, doi = {10.1007/3-540-44666-4_11}, journal = {Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques}, keywords = {approximation-algorithm, bin-packing, theory}, pages = {63--75}, posted-at = {2008-02-15 13:29:00}, priority = {2}, title = {Approximation Schemes for Ordered Vector Packing Problems}, url = {http://dx.doi.org/10.1007/3-540-44666-4_11}, year = {2001} }

TY - CHAP ID - citeulike:2385695 L3 - citeulike-article-id:2385695 N2 - In this paper we deal with the d-dimensional vector packing problem, which is a generalization of the classical bin packing problem in which each item has d distinct weights and each bin has d corresponding capacities. We address the case in which the vectors of weights associated with the items are totally ordered, i.e., given any two weight vectors a i, a j, either a i is componentwise not smaller than a j or a j is componentwise not smaller than a i, and construct an asymptotic polynomial-time approximation scheme for this case. As a corollary, we also obtain such a scheme for the bin packing problem with cardinality constraint, whose existence was an open question to the best of our knowledge. We also extend the result to instances with constant Dilworth number, i.e. instances where the set of items can be partitioned into a constant number of totally ordered subsets. We use ideas from classical and recent approximation schemes for related problems, as well as a nontrivial procedure to round an LP solution associated with the packing of the small items. JF - Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques EP - 75 TI - Approximation Schemes for Ordered Vector Packing Problems SP - 63 KW - approximation-algorithm KW - bin-packing KW - theory AU - Caprara, Alberto AU - Kellerer, Hans AU - Pferschy, Ulrich PY - 2001/// UR - http://dx.doi.org/10.1007/3-540-44666-4_11 ER -