Article

A polynomial time approximation scheme for the square packing problem

Authors:

Klaus Jansen,

Roberto Solis-ObaAuthors Info & Claims

IPCO'08: Proceedings of the 13th international conference on Integer programming and combinatorial optimization

Pages 184 - 198

Published: 26 May 2008 Publication History

Abstract

Given a set Q of squares with positive profits, the square packing problem is to select and pack a subset of squares of maximum profit into a rectangular bin R. We present a polynomial time approximation scheme for this problem, that for any value Ɛ > 0 finds and packs a subset Q′ ⊆ Q of profit at least (1 - Ɛ)OPT, where OPT is the profit of an optimum solution. This settles the approximability of the problem and improves on the previously best approximation ratio of 5/4 +Ɛ achieved by Harren's algorithm.

References

[1]

Bansal, N., Sviridenko, M.: Two-dimensional bin packing with one dimensional resource augmentation. Discrete Optimization (to appear)

Digital Library

Google Scholar

[2]

Coffman, E.G., Garey, M.R., Johnson, D.S., Tarjan, R.E.: Performance bounds for level-oriented two-dimensional packing algorithms. SIAM Journal on Computing 9, 808-826 (1980)

Crossref

Google Scholar

[3]

Cohen, R., Katzir, L., Raz, D.: An Efficient Approximation for the Generalized Assignment Problem. Information Processing Letters 100(4), 162-166

Digital Library

Google Scholar

[4]

Fishkin, A.V., Gerber, O., Jansen, K., Solis-Oba, R.: Packing weighted rectangles into a square. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 352-363. Springer, Heidelberg (2005)

Digital Library

Google Scholar

[5]

Harren, R.: Approximating the orthogonal knapsack problem for hypercubes. In: International Colloquium on Automata Languages and Programming (ICALP 2006), pp. 238-249 (2006)

Digital Library

Google Scholar

[6]

Jansen, K., Zhang, G.: Maximizing the total profit of rectangles packed into a rectangle. Algorithmica 47, 323-342 (2007)

Digital Library

Google Scholar

[7]

Kleitman, D.J., Krieger, M.M.: An optimal bound for two dimensional bin packing. In: Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science (FOCS 1975), pp. 163-168 (1975)

Digital Library

Google Scholar

[8]

Kenyon, C., Rémila, E.: A near-optimal solution to a two-dimensional cutting stock problem. Mathematics of Operations Research 25, 645-656 (2000)

Digital Library

Google Scholar

[9]

Lawler, E.: Fast approximation algorithms for knapsack problems. Mathematics of Operations Research 4, 339-356 (1979)

Digital Library

Google Scholar

[10]

Leung, J.Y.-T., Tam, T.W., Wong, C.S., Young, G.H., Chin, F.Y.L.: Packing squares into a square. Journal of Parallel and Distributed Computing 10, 271-275 (1990)

Digital Library

Google Scholar

[11]

Novotny, P.: On packing of squares into a rectangle. Archivum Mathematicum 32, 75-83 (1996)

Google Scholar

Cited By

View all

Heydrich SWiese A(2019)Faster Approximation Schemes for the Two-Dimensional Knapsack ProblemACM Transactions on Algorithms10.1145/333851215:4(1-28)Online publication date: 8-Aug-2019
https://dl.acm.org/doi/10.1145/3338512
Heydrich SWiese AKlein P(2017)Faster approximation schemes for the two-dimensional knapsack problemProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039692(79-98)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039692
Fekete SHoffmann H(2017)Online Square-into-Square PackingAlgorithmica10.1007/s00453-016-0114-277:3(867-901)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s00453-016-0114-2
Show More Cited By

A polynomial time approximation scheme for the square packing problem
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis

Recommendations

An Improved Approximation Scheme for Variable-Sized Bin Packing

The Variable-Sized Bin Packing Problem (abbreviated as VSBPP or VBP) is a well-known generalization of the NP-hard Bin Packing Problem (BP) where the items can be packed in bins of M given sizes. The objective is to minimize the total capacity of the ...
An improved approximation scheme for variable-sized bin packing
MFCS'12: Proceedings of the 37th international conference on Mathematical Foundations of Computer Science

The variable-sized bin packing problem (VBP) is a well-known generalization of the NP-hard bin packing problem (BP) where the items can be packed in bins of M given sizes. The objective is to minimize the total capacity of the bins used. We present an ...
Polynomial-Time Approximation Schemes for Circle and Other Packing Problems

We consider the problem of packing a set of circles into a minimum number of unit square bins. To obtain rational solutions, we use augmented bins of height $$1+\gamma $$1+ź, for some arbitrarily small number $$\gamma > 0$$ź>0. For this problem, we ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

IPCO'08: Proceedings of the 13th international conference on Integer programming and combinatorial optimization

May 2008

476 pages

ISBN:3540688862

Editors:
Andrea Lodi
DEIS, Università di Bologna, Bologna, Italy
,
Alessandro Panconesi
Dipartimento di Informatica, Università di Roma "La Sapienza", Rome, Italy
,
Giovanni Rinaldi
Istituto di Analisi dei Sistemi ed Informatica "Antonio Ruberti", CNR, Rome, Italy

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 26 May 2008

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
5
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Heydrich SWiese A(2019)Faster Approximation Schemes for the Two-Dimensional Knapsack ProblemACM Transactions on Algorithms10.1145/333851215:4(1-28)Online publication date: 8-Aug-2019
https://dl.acm.org/doi/10.1145/3338512
Heydrich SWiese AKlein P(2017)Faster approximation schemes for the two-dimensional knapsack problemProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039692(79-98)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039692
Fekete SHoffmann H(2017)Online Square-into-Square PackingAlgorithmica10.1007/s00453-016-0114-277:3(867-901)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1007/s00453-016-0114-2
Adamaszek AWiese AIndyk P(2015)A quasi-PTAS for the two-dimensional geometric knapsack problemProceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms10.5555/2722129.2722227(1491-1505)Online publication date: 4-Jan-2015
https://dl.acm.org/doi/10.5555/2722129.2722227
Dumitrescu ATóth C(2012)Packing anchored rectanglesProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095144(294-305)Online publication date: 17-Jan-2012
https://dl.acm.org/doi/10.5555/2095116.2095144
Chen MDósa GHan XZhou CBenko A(2011)2D knapsackProceedings of the 5th joint international frontiers in algorithmics, and 7th international conference on Algorithmic aspects in information and management10.5555/2021911.2021934(176-184)Online publication date: 28-May-2011
https://dl.acm.org/doi/10.5555/2021911.2021934
Harren R(2009)Approximation algorithms for orthogonal packing problems for hypercubesTheoretical Computer Science10.1016/j.tcs.2009.07.030410:44(4504-4532)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1016/j.tcs.2009.07.030
Bansal NCaprara AJansen KPrädel LSviridenko M(2009)A Structural Lemma in 2-Dimensional Packing, and Its Implications on ApproximabilityProceedings of the 20th International Symposium on Algorithms and Computation10.1007/978-3-642-10631-6_10(77-86)Online publication date: 5-Dec-2009
https://dl.acm.org/doi/10.1007/978-3-642-10631-6_10

Abstract

References

Cited By

Recommendations

An Improved Approximation Scheme for Variable-Sized Bin Packing

An improved approximation scheme for variable-sized bin packing

Polynomial-Time Approximation Schemes for Circle and Other Packing Problems

Comments

Information

Published In

Sponsors

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations