Improved approximation for two dimensional strip packing with polynomial bounded width
作者： Malin Rau , Klaus Jansen
DOI:
关键词:
摘要: We study the well-known two-dimensional strip packing problem. Given is a set of rectangular axis-parallel items and width $W$ with infinite height. The objective to find these into strip, which minimizes Lately, it has been shown that lower bound $3/2$ absolute approximation ratio can be beaten when we allow pseudo-polynomial running-time type $(n W)^{f(1/\varepsilon)}$. If polynomially bounded by number items, this polynomial running-time. present algorithm $4/3 +\varepsilon$ running time W)^{1/\varepsilon^{\mathcal{O}(2^{1/\varepsilon})}}$.
harvard.edu
arxiv.org参考文章(16)
Rolf Harren, Rob van Stee, Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. ,vol. 5687, pp. 177- 189 ,(2009) , 10.1007/978-3-642-03685-9_14
Andreas Wiese, Giorgi Nadiradze, On approximating strip packing with a better ratio than 3/2 symposium on discrete algorithms. pp. 1491- 1510 ,(2016) , 10.5555/2884435.2884537
Edward G Coffman, Jr, Michael R Garey, David S Johnson, Robert Endre Tarjan, Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms SIAM Journal on Computing. ,vol. 9, pp. 808- 826 ,(1980) , 10.1137/0209062
Brenda S Baker, Edward G Coffman, Jr, Ronald L Rivest, Orthogonal Packings in Two Dimensions SIAM Journal on Computing. ,vol. 9, pp. 846- 855 ,(1980) , 10.1137/0209064
Brenda S Baker, Donna J Brown, Howard P Katseff, A 54 algorithm for two-dimensional packing Journal of Algorithms. ,vol. 2, pp. 348- 368 ,(1981) , 10.1016/0196-6774(81)90034-1
Klaus Jansen, Ralf Thöle, Approximation Algorithms for Scheduling Parallel Jobs SIAM Journal on Computing. ,vol. 39, pp. 3571- 3615 ,(2010) , 10.1137/080736491
A. Steinberg, A Strip-Packing Algorithm with Absolute Performance Bound 2 SIAM Journal on Computing. ,vol. 26, pp. 401- 409 ,(1997) , 10.1137/S0097539793255801
Claire Kenyon, Eric Rémila, A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem Mathematics of Operations Research. ,vol. 25, pp. 645- 656 ,(2000) , 10.1287/MOOR.25.4.645.12118
Daniel D.K.D.B. Sleator, A 2.5 TIMES OPTIMAL ALGORITHM FOR PACKING IN TWO DIMENSIONS Information Processing Letters. ,vol. 10, pp. 37- 40 ,(1980) , 10.1016/0020-0190(80)90121-0
Igal Golan, Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms SIAM Journal on Computing. ,vol. 10, pp. 571- 582 ,(1981) , 10.1137/0210042