Paper Info
Title
Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems
Abstract
The multidimensional bin packing and vector bin packing problems are known to not have asymptotic polynomial-time approximation schemes (unless P = NP). Nevertheless, we show that: • Any smoothed (randomly perturbed) instance, and any instance from a class of other distributions, does have a polynomial-time probable approximation scheme. Namely, for any fixed ε 0, we exhibit a linear-time algorithm that finds a (1+ ε)-approximate packing with probability 1 - 2-Ω(n) over the space of random inputs. • There exists an oblivious algorithm that does not know from which distribution inputs come, and still asymptotically does almost as well as the previous algorithms. The oblivious algorithm outputs almost surely a (1 + ε)-approximation for every ε 0. • For vector bin packing, for each considered class of random instances, there exists an algorithm that in expected linear time computes a (1 + ε)-approximation, for any fixed ε 0. To achieve these results we develop a multidimensional version of the one-dimensional rounding technique introduced by Fernadez de la Vega and Lueker. Our results generalize Karp, Luby and Marchetti-Spaccamela's results on approximatibility of random instances of multidimensional bin packing to a much wider class of distributions.
Year
DOI
Venue
2007
10.1145/1283383.1283513
SODA
Keywords
Field
DocType
independent set,bin packing,linear time,polynomial time,bin packing problem,polynomial time approximation scheme
Discrete mathematics,Combinatorics,Packing problems,Polynomial,Rounding,Independent set,Set packing,Almost surely,Time complexity,Bin packing problem,Mathematics
Conference
ISBN
Citations 
PageRank 
978-0-89871-624-5
10
0.60
References 
Authors
12
2
Name
Order
Citations
PageRank
David R. Karger1193672233.64
Krzysztof Onak249325.90