组合优化若干经典问题新进展

Abstract

Abstract: Combinatorial optimization, as an interdiscipline of operations research and computer science, has been developing since the mid-20th century. It characters optimization problems with discrete structures, and explores their solution methods. Due to the structural divergence in discrete problems, there has been a wide variety of methodologies and techniques. In this paper, we briefly introduce a number of fundamental problems in combinatorial optimization, and present the recent achievements together with some open problems.

Key words: combinatorial optimization, computational complexity, approximation algorithms, polyhedral combinatorics, matriod

CLC Number:

O221.7

CHEN Xujin, XU Dachuan, ZHANG Guochuan. New perspectives of several fundamental problems in combinatorial optimization[J]. Operations Research Transactions, 2014, 18(1): 149-158.

References

Schrijver A. Combinatorial Optimization: Polyhedra and Efficiency [M]. Berlin: Springer-Verlag, 2003.

Korte B, Vygen J.Combinatorial Optimization: Theory and Algorithms [M]. Berlin: Springer-Verlag, 2012.

Vazirani V V. Approximation Algorithms [M]. Berlin: Springer-Verlag, 2001.

Williamson D P, Shmoys D B. The Design of Approximation Algorithms [M]. New York: Cambridge University Press, 2011.

Arora S, Barak B. Computational Complexity: A Modern Approach [M]. New York: Cambridge University Press, 2009.

Johnson D S. Near-optimal bin packing algorithms [D]. Cambridge: Massachusetts Institute of Technology, 1973.

Yue M Y. A simple proof of the inequality FFD(L)\le 11/9 OPT(L)+1,\ \forall L, for the FFD bin-packing algorithm [J]. Acta Mathematicae Applicatae Sinica, 1991, 7(4): 321-331.

Dosa G, Li R H, Han X, et al. Tight absolute bound for first fit decreasing bin-packing: FFD(l)\le 11/9 OPT(L) + 6/9 [J]. Theoretical Computer Science, 2013, 510: 13-61.

Dosa 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.

Seiden S S. On the online bin packing problem [J]. Journal of the ACM, 2002, 49: 640-671.

Rothvo\ss T. Approximating bin packing within O(logOPTloglogOPT) bins [C]//Proceedings of the 54th Annual Symposium on Foundations of Computer Science (FOCS), 2013, 20-29.

Goemans M X, Rothvo{\ss 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.

Bansal N, Khan A. Improved approximation algorithm for two-dimensional bin packing [C]//Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, 2014.

Han X, Chin F Y L, Ting H F, et al. A new upper bound 2.554~5 on 2D online bin packing [J]. ACM Transactions on Algorithms, 2011, 7(4): 50.

Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem [R]. [s.l.]: DTIC Document, 1976.

Hoogeveen J A. Analysis of Christofides' heuristic: Some paths are more difficult than cycles [J]. Operations Research Letters, 1991, 10(5): 291-295.

An H C, Kleinberg R, Shmoys D B. Improving Christofides' algorithm for the st path TSP [C]//Proceedings of the 44th Symposium on Theory of Computing (STOC), 2012, 875-886.

Seb{\H{o A. Eight-fifth approximation for the path TSP [C]//Proceedings of Integer Programming and Combinatorial Optimization (IPCO), 2013, 362-374.

Shmoys D B, Tardos {\'E, Aardal K. Approximation algorithms for facility location problems [C]//Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), 1997, 265-274.

Li S. A 1.488 approximation algorithm for the uncapacitated facility location problem [C]//Proceedings of the 38th International Conference on Automata, Languages and Programming (ICALP), 2011, 77-88.

Li S, Svensson O. Approximating k-median via pseudo-approximation [C]//Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), 2013, 901-910.

Zelikovsky A Z. An 11/6-approximation algorithm for the network Steiner problem [J]. Algorithmica, 1993, 9(5): 463-470.

Byrka J, Grandoni F, Rothvo{\ss T, et al. An improved LP-based approximation for Steiner tree [C]//Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), 2010, 583-592.

Goemans M X, Williamson D P. A general approximation technique for constrained forest problems [J]. SIAM Journal on Computing, 1995, 24(2): 296-317.

Archer A, Bateni M, Hajiaghayi M, et al. Improved approximation algorithms for Prize-Collecting Steiner Tree and TSP [J]. SIAM Journal on Computing, 2011, 40(2): 309-332.

Eisenbrand F, Grandoni F, Rothvo{\ss T, et al. Connected facility location via random facility sampling and core detouring [J]. Journal of Computer and System Sciences, 2010, 76(8): 709-726.

Goemans M X, Williamson D P. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J]. Journal of the ACM, 1995, 42(6): 1115-1145.

Goemans M X, Williamson D P. Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming [C]//Proceedings of the 33rd Annual ACM symposium on Theory of computing (STOC), 2001, 443-452.

Raghavendra P. Optimal algorithms and inapproximability results for every CSP? [C]//Proceedings of the 40th Annual ACM symposium on Theory of Computing (STOC), 2008, 245-254.

Khot S. On the power of unique 2-prover 1-round games [C]//Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), 2002, 767-775.

Lasserre J B. Global optimization with polynomials and the problem of moments [J]. SIAM Journal on Optimization, 2001, 11(3): 796-817.

Raghavendra P, Tan N. Approximating CSPs with global cardinality constraints using SDP hierarchies [C]//Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012, 373-387.

Austrin P, Benabbas S, Georgiou K. Better balance by being biased: a 0.8776-approximation for Max Bisection [C]// Proceedings of the 24th Annual ACM-SIAM Symposium onDiscrete Algorithms (SODA), 2013, 277-294.

Lokshtanov D, Marx D, Saurabh S. Lower bounds based on the exponential time hypothesis [J]. Bulletin of the EATCS, 2011, 105: 41-72.

Chen X, Hu X, Zang W. Dual integrality in combinatorial optimization [M]//Handbook of Combinatorial Optimization, Berlin: Springer-Verlag, 2013, 995-1063.

Ding G, Feng L, Zang W. The complexity of recognizing linear systems with certain integrality properties [J]. Mathematical Programming, Series A, 2008, 114: 321-334.

[1]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.
[2]	LIU Yafeng. Two optimization problems in wireless communication system design and related optimization methods [J]. Operations Research Transactions, 2019, 23(3): 47-62.
[3]	HE Cheng, HAN Xinxin. Two-agent scheduling on an unbounded parallel-batching machine to minimize maximum cost and makespan [J]. Operations Research Transactions, 2018, 22(3): 109-116.
[4]	XING Wenxun. Complexity concepts for combinatorial and continuous optimization problems [J]. Operations Research Transactions, 2017, 21(2): 39-45.
[5]	GAO Jingzhen, GAO Bo. Chinese postman problem over 50 years [J]. Operations Research Transactions, 2013, 17(1): 17-28.
[6]	XU Jian-Teng, ZHANG Yu-Zhong, BAI Qing-Guo. A Polynomial Time Algorithm for the Economic Lot-size Problem with Multiple Suppliers and Multiple Retailers [J]. Operations Research Transactions, 2011, 15(4): 102-114.

New perspectives of several fundamental problems in combinatorial optimization

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 6

Recommended Articles

Metrics

Comments