English

运筹学学报 >

2022 , Vol. 26 >Issue 1: 69 - 84

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2022.01.005

 

经典一维装箱问题近似算法的研究进展

展开
  • 1. 浙江大学数学科学学院, 浙江杭州 310058
    2. 浙江大学计算机科学与技术学院, 浙江杭州 310058
陈婳  E-mail: chenhua_by@zju.edu.cn

收稿日期: 2021-06-07

  网络出版日期: 2022-03-14

基金资助

国家自然科学基金(11771365)

收起

A survey on approximation algorithms for one dimensional bin packing

Expand
  • 1. School of Mathematical Sciences, Zhejiang University, Hangzhou 310058, Zhejiang, China
    2. College of Computer Sciences and Technology, Zhejiang University, Hangzhou 310058, Zhejiang, China

Received date: 2021-06-07

  Online published: 2022-03-14

Fold

摘要

自20世纪70年代开始，随着计算复杂性理论的建立，近似算法逐渐成为组合优化的重要研究方向。作为第一批研究对象，装箱问题引起了组合优化领域学者的极大关注。装箱问题模型简单、拓展性强，广泛出现在各种带容量约束的资源分配问题中。除了在物流装载和材料切割等方面愈来愈重要的应用外，装箱算法的任何理论突破都关乎到整个组合优化领域的发展。直到今天，对装箱问题近似算法的研究仍如火如荼。本文主要针对一维模型，简述若干经典Fit算法的发展历程，分析基于线性规划松弛的近似方案的主要思路，总结当前的研究现状并对未来的研究提供一些参考建议。

关键词： 装箱问题; 近似算法; 线性规划松弛

本文引用格式

陈婳, 张国川 . 经典一维装箱问题近似算法的研究进展[J]. 运筹学学报, 2022 , 26(1) : 69 -84 . DOI: 10.15960/j.cnki.issn.1007-6093.2022.01.005

Abstract

With the emergence of computational complexity theory, the study of approximation algorithms has gradually become an important field in combinatorial optimization since the 1970s. As one of the classic combinatorial optimization problems, bin packing has attracted great attention. It can be widely found in various resource allocation problems with capacity constraints. Its more and more important applications including logistics loading and material cutting aside, any theoretical breakthrough of bin packing algorithms is related to the development of the whole combinatorial optimization. At present, the research on approximation algorithms of bin packing is still popular. This paper briefly introduces the process of some classic Fit algorithms, analyzes the main ideas of approximation schemes based on linear programming relaxation, reviews the state of the art, and provides some suggestions for future research.

Key words： bin packing; approximation algorithms; linear programming relaxation

参考文献

1 Yue M Y . A simple proof of the inequality FFD (L) ≤ 11/9OPT (L) +1, ?L for the FFD bin-packing algorithm[J]. Acta Mathematicae Applicatae Sinica, 1991, 7 (4): 321- 331.
2 Eisemann K . The trim problem[J]. Management Science, 1957, 3 (3): 279- 284.
3 Ullman J D. The performance of a memory allocation algorithm[R]. Princeton: Princeton University, 1971.
4 Johnson D S. Near-optimal bin packing algorithms[D]. Cambridge: Massachusetts Institute of Technology, 1973.
5 Garey M R, Johnson D S. Approximation algorithms for bin packing problems: A survey[M]//Analysis and Design of Algorithms in Combinatorial Optimization, New York: Springer, 1981: 147-172.
6 Coffman E G, Garey M R, Johnson D S. Approximation algorithms for bin-packing-an updated survey[M]//Algorithm Design for Computer System Design, New York: Springer, 1984: 49-106.
7 Coffman E G , Garey M R , Johnson D S . Approximation algorithms for bin packing: A survey[J]. Approximation Algorithms for NP-hard Problems, 1996, 46- 93.
8 Coffman E G, Csirik J, Galambos G, et al. Bin packing approximation algorithms: Survey and classification[M]. Handbook of Combinatorial Optimization, 2013: 455-531.
9 Johnson D S . Fast algorithms for bin packing[J]. Journal of Computer and System Sciences, 1974, 8 (3): 272- 314.
10 Johnson D S , Demers A , Ullman J D , et al. Worst-case performance bounds for simple onedimensional packing algorithms[J]. SIAM Journal on Computing, 1974, 3 (4): 299- 325.
11 Garey M R , Graham R L , Johnson D S , et al. Resource constrained scheduling as generalized bin packing[J]. Journal of Combinatorial Theory, Series A, 1976, 21 (3): 257- 298.
12 Dósa G, Sgall J. First fit bin packing: A tight analysis[C]//Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), 2013: 538-549.
13 Dósa G, Sgall J. Optimal analysis of best fit bin packing[C]//Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), 2014: 429-441.
14 Csirik J , Imreh B . On the worst-case performance of the NkF bin-packing heuristic[J]. Acta Cybernetica, 1989, 9 (2): 89- 105.
15 Mao W . Tight worst-case performance bounds for next-k-fit bin packing[J]. SIAM Journal on Computing, 1993, 22 (1): 46- 56.
16 Mao W . Besk-k-Fit bin packing[J]. Computing, 1993, 50 (3): 265- 270.
17 Zhang G , Yue M . Tight performance bound of AFBk bin packing[J]. Acta Mathematicae Applicatae Sinica, 1997, 13 (4): 443- 446.
18 Csirik J , Johnson D S . Bounded space on-line bin packing: Best is better than first[J]. Algo rithmica, 2001, 31 (2): 115- 138.
19 Lee C C , Lee D T . A simple on-line bin-packing algorithm[J]. Journal of the ACM, 1985, 32 (3): 562- 572.
20 Galambos G . Parametric lower bound for on-line bin-packing[J]. SIAM Journal on Algebraic Discrete Methods, 1986, 7 (3): 362- 367.
21 Balogh J , Békési J , Dósa G , et al. A new lower bound for classic online bin packing[J]. Algorithmica, 2021, 83 (7): 2047- 2062.
22 Balogh J, Békési J, Dósa G, et al. A new and improved algorithm for online bin packing[C]//Proceedings of the 26th European Symposium on Algorithms (ESA), 2018: 1-5: 14.
23 Baker B S , Coffman E G . A tight asymptotic bound for next-fit-decreasing bin-packing[J]. SIAM Journal on Algebraic Discrete Methods, 1981, 2 (2): 147- 152.
24 Garey M R, Graham R L, Ullman J D. Worst-case analysis of memory allocation algorithms[C]//Proceedings of the 4th Annual ACM Symposium on Theory of Computing (STOC), 1972: 143-150.
25 Baker B S . A new proof for the first-fit decreasing bin-packing algorithm[J]. Journal of Algo rithms, 1985, 6 (1): 49- 70.
26 Li R , Yue M Y . The proof of FFD (L) 611=9OPT (L) +7=9[J]. Chinese Science Bulletin, 1997, 42 (15): 1262- 1265.
27 Dósa G. The tight bound of first fit decreasing bin-packing algorithm is FFD (I)611=9OPT (I)+6=9[C]//International Symposium on Combinatorics, Algorithms, Probabilistic and Experimen tal Methodologies, 2007: 1-11.
28 Garey M R , Johnson D S . Computers and Intractability: A Guide to the Theory of NP Completeness[M]. New York: WH Freeman and Company, 1979.
29 Zhang G , Cai X , Wong C K . Linear time-approximation algorithms for bin packing[J]. Oper ations Research Letters, 2000, 26 (5): 217- 222.
30 Fernandez de la Vega W , Lueker G S . Bin packing can be solved within 1+ "ε" in linear time[J]. Combinatorica, 1981, 1 (4): 349- 355.
31 Williamson D P , Shmoys D B . The Design of Approximation Algorithms[M]. Cambridge: Cam bridge University press, 2011.
32 Gr?tschel M , Lovász L , Schrijver A . The ellipsoid method and its consequences in combinatorial optimization[J]. Combinatorica, 1981, 1 (2): 169- 197.
33 Karmarkar N, Karp R M. An efficient approximation scheme for the one-dimensional bin packing problem[C]//Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS), 1982: 312-320.
34 Eisenbrand F, Pálv?lgyi D, Rothvoss T. Bin packing via discrepancy of permutations[C]//Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011: 476-481.
35 Newman A, Neiman O, Nikolov A. Beck's three permutations conjecture: A counterexample and some consequences[C]//Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS), 2012: 253-262.
36 Eisenbrand F , Pálv?lgyi D , Rothvoss T . Bin packing via discrepancy of permutations[J]. ACM Transactions on Algorithms, 2013, 9 (3): 1- 15.
37 Rothvoss T. Approximating bin packing within O$ (\log \text{OPT}* \log \log \text{OPT}) $ bins[C]//Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), 2013: 20-29
38 Hoberg R, Rothvoss T. A logarithmic additive integrality gap for bin packing[C]//Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017: 2616-2625.
39 Lovett S , Meka R . Constructive discrepancy minimization by walking on the edges[J]. SIAM Journal on Computing, 2015, 44 (5): 1573- 1582.
40 Jansen K, Solis-Oba R. An OPT +1 algorithm for the cutting stock problem with constant number of object lengths[C]//Proceedings of the 14th International Conference on Integer Programming and Combinatorial Optimization (IPCO), 2010: 438-449.
41 Goemans M X, Rothvoss T. Polynomiality for bin packing with a constant number of item types[C]//Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014: 830-839.
42 Friesen D K , Langston M A . A storage-size selection problem[J]. Information Processing Letters, 1984, 18 (5): 295- 296.
43 Friesen D K , Langston M A . Variable sized bin packing[J]. SIAM Journal on Computing, 1986, 15 (1): 222- 230.
44 Epstein L , Levin A . An APTAS for generalized cost variable-sized bin packing[J]. SIAM Journal on Computing, 2008, 38 (1): 411- 428.
45 Jansen K , ?hring S . Approximation algorithms for time constrained scheduling[J]. Information and Computation, 1997, 132 (2): 85- 108.
46 Jansen K . An approximation scheme for bin packing with conflicts[J]. Journal of Combinatorial Optimization, 1999, 3 (4): 363- 377.
47 Epstein L , Levin A . On bin packing with conflicts[J]. SIAM Journal on Optimization, 2008, 19 (3): 1270- 1298.
48 Koutsoupias E, Papadimitriou C. Worst-case equilibria[C]//Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 1999: 404-413.
49 Zhang C, Zhang G. Cost-sharing mechanisms for selfish bin packing[C]//Proceedings of the 11th International Conference on Combinatorial Optimization and Applications (COCOA), 2017: 355-368.
Options
文章导航

/

〈 〉