Improved approximation algorithms for multidimensional bin packing problems

摘要: In this paper we introduce a new general framework for set covering problems, based on the combination of randomized rounding (near-)optimal solution linear programming (LP) relaxation, leading to partial integer solution, and application well-behaved approximation algorithm complete solution. If value returned by latter can be bounded in suitable way, as is case most relevant generalizations bin packing, method leads improved guarantees, along with proof tighter integrality gaps LP relaxation. Applying our obtain polynomial-time d-dimensional vector packing guarantee arbitrarily close ln d + 1. For = 2, 1.693 ..., i.e., break natural 2 "barrier" case. Moreover, small values notable improvement over previously-known O(ln d) Chekuri Khanna (2004). 2-dimensional without rotations, construct algorithms performance 1.525..., improving upon previous epsiv Jansen Zhang (2004) problem rotations and1.691... Caprara (2002) rotations. The previously-unknown key property used proofs follows from retrospective analysis implications landmark scheme Fernandez de la Vega Lueker (1981). We prove that their "subset oblivious", which numerous applications. Another byproduct an solves well-known configuration within factor (1 epsiv) any gt; 0. Interestingly, do it using approximate separation oracle, would correspond geometric knapsack. Although optimization are equivalent (M. Grotschel et al, 1988) existence remains open, able design since its objective function unweighed