An approximation algorithm for square packing

An approximation algorithm for square packing

0.00 Avg rating0 Votes
Article ID: iaor2005738
Country: Netherlands
Volume: 32
Issue: 6
Start Page Number: 535
End Page Number: 539
Publication Date: Nov 2004
Journal: Operations Research Letters
Authors:
Keywords: packing
Abstract:

We consider the problem of packing squares into bins which are unit squares, where the goal is to minimize the number of bins used. We present an algorithm for this problem with an absolute worst-case ratio of 2, which is optimal provided P≠NP.

Reviews

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