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

Improved Approximation Algorithms for Multidimensional Bin Packing Problems / N. Bansal; A. Caprara; M. Sviridenko. - STAMPA. - (2006), pp. 697-708. (Intervento presentato al convegno 47-th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006) tenutosi a San Francisco nel 22-24 Ottobre 2006).

Improved Approximation Algorithms for Multidimensional Bin Packing Problems

CAPRARA, ALBERTO;
2006

Abstract

In this paper we introduce a new general framework for set covering problems, based on the combination of randomized rounding of the (near-)optimal solution of the Linear Programming (LP) relaxation, leading to a partial integer solution, and the application of a well-behaved approximation algorithm to complete this solution. If the value of the solution returned by the latter can be bounded in a suitable way, as is the case for the most relevant generalizations of bin packing, the method leads to improved approximation guarantees, along with a proof of tighter integrality gaps for the LP relaxation. Applying our general framework we obtain a polynomial-time randomized algorithm for d-dimensional vector packing with approximation guarantee arbitrarily close to ln d + 1. For d=2, this value is 1.693..., i.e., we break the natural 2 "barrier'' for this case. Moreover, for small values of d this is a notable improvement over the previously-known O(ln d) guarantee. For 2-dimensional bin packing with and without rotations, we construct algorithms with performance guarantee arbitrarily close to 1.525..., improving upon previous algorithms with performance guarantee of 2 for the problem with rotations and 1.691... for the problem without rotations. The previously-unknown key property used in our proofs follows from a retrospective analysis of the implications of the landmark bin packing approximation scheme by Fernandez de la Vega and Lueker. We prove that their approximation scheme is "subset oblivious'', which leads to numerous applications. Another byproduct of our paper is an algorithm that solves a well-known configuration LP for 2-dimensional bin packing within a factor of 1+epsilon for any epsilon>0. Interestingly, we do it without using an approximate separation oracle, which would correspond to a well-known geometric 2-dimensional knapsack. Although separation and optimization are equivalent and the existence of an approximation scheme for the separation problem remains open, we are able to design an approximation scheme for the configuration LP since its objective function is unweighed.
2006
Proceedings of the 47-th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006)
697
708
Improved Approximation Algorithms for Multidimensional Bin Packing Problems / N. Bansal; A. Caprara; M. Sviridenko. - STAMPA. - (2006), pp. 697-708. (Intervento presentato al convegno 47-th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006) tenutosi a San Francisco nel 22-24 Ottobre 2006).
N. Bansal; A. Caprara; M. Sviridenko
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/40497
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 65
  • ???jsp.display-item.citation.isi??? 38
social impact