Back to Search
Start Over
2D knapsack: Packing squares.
- Source :
-
Theoretical Computer Science . Oct2013, Vol. 508, p35-40. 6p. - Publication Year :
- 2013
-
Abstract
- Abstract: In this paper, we study a two-dimensional knapsack problem: packing squares as many as possible into a unit square. Our results are the following: [(i)] we propose an algorithm called IHS (Increasing Height Shelf), and prove that the packing is optimal if in an optimal packing there are at most 5 squares, and this upper bound is sharp; [(ii)] if all the squares have side length at most , we propose a simple and fast algorithm with an approximation ratio in time ; [(iii)] we give an EPTAS for the problem, where the previous result in Jansen and Solis-Oba (2008) [16] is a PTAS, not an EPTAS. However our approach does not work on the previous model of Jansen and Solis-Oba (2008) [16], where each square has an arbitrary weight. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 508
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 91630143
- Full Text :
- https://doi.org/10.1016/j.tcs.2012.07.035