An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing

An approximation algorithm with absolute worst-case performance ratio 2 for two-dimensional vector packing

0.00 Avg rating0 Votes
Article ID: iaor2004393
Country: Netherlands
Volume: 31
Issue: 1
Start Page Number: 35
End Page Number: 41
Publication Date: Jan 2003
Journal: Operations Research Letters
Authors: ,
Keywords: bin packing, geometry
Abstract:

The two-dimensional vector packing problem is the generalization of the classical one-dimensional bin packing problem to two dimensions. While an asymptotic polynomial time approximation scheme has been designed for one-dimensional bin packing, the existence of an asymptotic polynomial time approximation scheme for two dimensions would imply P=NP. The existence of an approximation algorithm for the two-dimensional vector packing problem with an asymptotic performance guarantee 2 was an open problem so far. In this paper we present an O(n log n) time for two-dimensional vector packing with absolute performance guarantee 2.

Reviews

Required fields are marked *. Your email address will not be published.