Article

New approximability results for 2-dimensional packing problems

Authors:

Roberto Solis-ObaAuthors Info & Claims

MFCS'07: Proceedings of the 32nd international conference on Mathematical Foundations of Computer Science

Pages 103 - 114

Published: 26 August 2007 Publication History

Abstract

The strip packing problem is to pack a set of rectangles into a strip of fixed width and minimum length. We present asymptotic polynomial time approximation schemes for this problem without and with 90° rotations. The additive constant in the approximation ratios of both algorithms is 1, improving on the additive term in the approximation ratios of the algorithm by Kenyon and Rémila (for the problem without rotations) and Jansen and van Stee (for the problem with rotations), both of which have a larger additive constant O(1/ε²), ε > 0.

The algorithms were derived from the study of the rectangle packing problem: Given a set R of rectangles with positive profits, the goal is to find and pack a maximum profit subset of R into a unit size square bin [0, 1] × [0, 1]. We present algorithms that for any value ∈ > 0 find a subset R′ ⊆ R of rectangles of total profit at least (1 - ∈)OPT, where OPT is the profit of an optimum solution, and pack them (either without rotations or with 90° rotations) into the augmented bin [0, 1]×[0,1+∈].

References

[1]

Bansal, N., Sviridenko, M.: Two-dimensional bin packing with one dimensional resource augmentation. Discrete Optimization 4, 143-153 (2007)

[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)

[3]

de la Vega, W.F., Lueker, G.S.: Bin packing can be solved within 1+epsilon in linear time. Combinatorica 1(4), 349-355 (1981)

[4]

Fishkin, A.V., Gerber, O., Jansen, K.: On weighted rectangle packing with large resources. In: Conference Theoretical Computer Science (TCS 2004), pp. 237-250 (2004)

[5]

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)

[6]

Garey, M.R., D. S., Johnson.: Computers and Intractability: A guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco (1979)

[7]

Harren, R.: Approximating the orthogonal knapsack problem for hypercubes. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4051, pp. 238-249. Springer, Heidelberg (2006)

[8]

Jansen, K., van Stee, R.: On strip packing with rotations. In: ACM Symposium on Theory of Computing. STOC 2005, pp. 755-761 (2005)

[9]

Jansen, K., Zhang, G.: On rectangle packing: maximizing benefits. In: ACM-SIAM Symposium on Discrete Algorithms. SODA 2004, pp. 197-206 (2004)

[10]

Jansen, K., Zhang, G.: Maximizing the number of packed rectangles. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 362-371. Springer, Heidelberg (2004)

[11]

Karmarkar, M., Karp, R.M.: An efficient approximation scheme for the onedimensional bin-packing problem. In: IEEE Symposium on Foundations of Computer Science. FOCS 1982, pp. 312-320 (1982)

[12]

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

[13]

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

[14]

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

[15]

Schiermeyer, I.: Reverse-fit: a 2-optimal algorithm for packing rectangles. In: van Leeuwen, J. (ed.) ESA 1994. LNCS, vol. 855, pp. 290-299. Springer, Heidelberg (1994)

[16]

Steinberg, A.: A strip-packing algorithm with absolute performance bound two. SIAM Journal on Computing 26, 401-409 (1997)

Cited By

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

New approximability results for 2-dimensional packing problems
1. Mathematics of computing
  1. Mathematical analysis
    1. Functional analysis
2. Theory of computation

Recommendations

New approximability results for two-dimensional bin packing
SODA '13: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms

We study the two-dimensional bin packing problem: Given a list of n rectangles the objective is to find a feasible, i.e. axis-parallel and non-overlapping, packing of all rectangles into the minimum number of unit sized squares, also called bins. Our ...
New Approximability Results for Two-Dimensional Bin Packing

We study the two-dimensional bin packing problem: Given a list of $$n$$n rectangles the objective is to find a feasible, i.e. axis-parallel and non-overlapping, packing of all rectangles into the minimum number of unit sized squares, also called bins. ...
New approximability and inapproximability results for 2-dimensional Bin Packing
SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms

We study the 2-dimensional generalization of the classical Bin Packing problem: Given a collection of rectangles of specified size (width, height), the goal is to pack these into minimum number of square bins of unit size. A long history of results ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

MFCS'07: Proceedings of the 32nd international conference on Mathematical Foundations of Computer Science

August 2007

761 pages

ISBN:354074455X

Editors:
Ludek Kučera
Charles University, Faculty of Mathematics and Physics, Department of Applied Mathematics, Praha, Czech Republic
,
Antonín Kučera
Masaryk University, Faculty of Informatics, Department of Computer Science, Brno, Czech Republic

Sponsors

EATCS: European Association for Theoretical Computer Science

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 26 August 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
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

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
Alamdari SBiedl TChan TGrant EJampani KKeshav SLubiw APathak V(2013)Smart-Grid electricity allocation via strip packing with slicingProceedings of the 13th international conference on Algorithms and Data Structures10.1007/978-3-642-40104-6_3(25-36)Online publication date: 12-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-40104-6_3
Jansen KBlelloch GHerlihy M(2012)A(3/2+ε) approximation algorithm for scheduling moldable and non-moldable parallel tasksProceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures10.1145/2312005.2312048(224-235)Online publication date: 25-Jun-2012
https://dl.acm.org/doi/10.1145/2312005.2312048
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
Harren RStee R(2009)Improved Absolute Approximation Ratios for Two-Dimensional Packing ProblemsProceedings of the 12th International Workshop and 13th International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-03685-9_14(177-189)Online publication date: 21-Aug-2009
https://dl.acm.org/doi/10.1007/978-3-642-03685-9_14
Jansen KThöle R(2008)Approximation Algorithms for Scheduling Parallel JobsProceedings of the 35th international colloquium on Automata, Languages and Programming - Volume Part I10.1007/978-3-540-70575-8_20(234-245)Online publication date: 7-Jul-2008
https://dl.acm.org/doi/10.1007/978-3-540-70575-8_20
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten