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

doi:10.15960/j.cnki.issn.1007-6093.2022.01.005

Abstract

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

CLC Number:

O221.7

Hua CHEN, Guochuan ZHANG. A survey on approximation algorithms for one dimensional bin packing[J]. Operations Research Transactions, 2022, 26(1): 69-84.

References 49

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. doi: 10.1007/BF02009683
2	Eisemann K . The trim problem[J]. Management Science, 1957, 3 (3): 279- 284. doi: 10.1287/mnsc.3.3.279
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. doi: 10.1016/S0022-0000(74)80026-7
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. doi: 10.1137/0203025
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. doi: 10.1016/0097-3165(76)90001-7
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. doi: 10.1137/0222004
16	Mao W . Besk-k-Fit bin packing[J]. Computing, 1993, 50 (3): 265- 270. doi: 10.1007/BF02243816
17	Zhang G , Yue M . Tight performance bound of AFBk bin packing[J]. Acta Mathematicae Applicatae Sinica, 1997, 13 (4): 443- 446. doi: 10.1007/BF02009554
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. doi: 10.1145/3828.3833
20	Galambos G . Parametric lower bound for on-line bin-packing[J]. SIAM Journal on Algebraic Discrete Methods, 1986, 7 (3): 362- 367. doi: 10.1137/0607041
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. doi: 10.1007/s00453-021-00818-7
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. doi: 10.1137/0602019
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. doi: 10.1016/0196-6774(85)90018-5
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. doi: 10.1007/BF02882754
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. doi: 10.1016/S0167-6377(99)00077-2
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. doi: 10.1007/BF02579456
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. doi: 10.1007/BF02579273
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. doi: 10.1137/130929400
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. doi: 10.1016/0020-0190(84)90010-3
43	Friesen D K , Langston M A . Variable sized bin packing[J]. SIAM Journal on Computing, 1986, 15 (1): 222- 230. doi: 10.1137/0215016
44	Epstein L , Levin A . An APTAS for generalized cost variable-sized bin packing[J]. SIAM Journal on Computing, 2008, 38 (1): 411- 428. doi: 10.1137/060670328
45	Jansen K , Öhring S . Approximation algorithms for time constrained scheduling[J]. Information and Computation, 1997, 132 (2): 85- 108. doi: 10.1006/inco.1996.2616
46	Jansen K . An approximation scheme for bin packing with conflicts[J]. Journal of Combinatorial Optimization, 1999, 3 (4): 363- 377. doi: 10.1023/A:1009871302966
47	Epstein L , Levin A . On bin packing with conflicts[J]. SIAM Journal on Optimization, 2008, 19 (3): 1270- 1298. doi: 10.1137/060666329
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.

[1]	Jianping LI, Lijian CAI, Junran LICHEN, Pengxiang PAN. The constrained multi-sources eccentricity augmentation problems [J]. Operations Research Transactions, 2022, 26(1): 60-68.
[2]	JU Jiachen, LIU Qian, ZHANG Zhao, ZHOU Yang. A local search analysis for the uniform capacitated $k$-means problem with penalty [J]. Operations Research Transactions, 2022, 26(1): 113-124.
[3]	Xiaowei LI, Xiayan CHENG, Rongheng LI. An approximation algorithm for Robust k-product facility location problem with linear penalties [J]. Operations Research Transactions, 2021, 25(4): 31-44.
[4]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[5]	CHEN Xujin, XU Dachuan, ZHANG Guochuan. New perspectives of several fundamental problems in combinatorial optimization [J]. Operations Research Transactions, 2014, 18(1): 149-158.

A survey on approximation algorithms for one dimensional bin packing

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

References 49

Related Articles 5

Recommended Articles

Metrics

Comments