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

摘要/Abstract

摘要： 组合优化是20世纪中后期发展起来的一个运筹学与计算机科学交叉学科分支, 研究具有离散结构的优化问题解的性质和求解方法. 由于不同离散问题的结构差异, 出现了各种各样的研究手段和技巧. 针对组合优化的若干经典问题, 简述了算法和复杂性理论的研究进展.

关键词: 组合优化, 计算复杂性, 近似算法, 多面体组合, 拟阵

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

中图分类号:

O221.7

陈旭瑾，徐大川，张国川. 组合优化若干经典问题新进展[J]. 运筹学学报, 2014, 18(1): 149-158.

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

参考文献

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]	张玉忠. 工件可拒绝排序问题综述[J]. 运筹学学报, 2020, 24(2): 111-130.
[2]	刘晓霞, 余山杉, 罗文昌. 工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法[J]. 运筹学学报, 2020, 24(1): 131-139.
[3]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[4]	张国川, 陈林. 负载均衡问题[J]. 运筹学学报, 2019, 23(3): 1-14.
[5]	刘亚锋. 无线通信系统设计中的两个优化问题和相关优化方法[J]. 运筹学学报, 2019, 23(3): 47-62.
[6]	姜燕君, 徐大川, 张冬梅. 平方度量动态设施选址问题的近似算法[J]. 运筹学学报, 2018, 22(3): 49-58.
[7]	余善恩, 徐文洋, 刘光宇. 圆形区域分散布局问题研究[J]. 运筹学学报, 2018, 22(3): 132-138.
[8]	何程, 韩鑫鑫. 同时最小化最大费用和最大完工时间的双代理无界平行分批排序[J]. 运筹学学报, 2018, 22(3): 109-116.
[9]	王一水, 徐大川, 吴晨晨. 关联聚类问题的半定规划舍入算法[J]. 运筹学学报, 2018, 22(1): 67-76.
[10]	陈光亭, 陈蕾, 张安, 陈永. 可转包两台流水作业机排序的近似算法[J]. 运筹学学报, 2016, 20(4): 109-114.
[11]	仲维亚, 马晓茹. 带有运输且加工具有灵活性的无等待流水作业排序问题[J]. 运筹学学报, 2016, 20(4): 93-101.
[12]	孙婷, 李改弟, 徐文青. 最大割问题和最大平分割问题基于半定规划松弛的近似算法[J]. 运筹学学报, 2016, 20(3): 21-32.
[13]	方芮, 罗文昌. 带惩罚的容错设施布局问题的近似算法[J]. 运筹学学报, 2016, 20(2): 69-78.
[14]	付天文, 涂卓卓, 魏伯洋. 基于新型负指数期望效用的投资组合选择模型[J]. 运筹学学报, 2016, 20(1): 1-18.
[15]	闫林成, 肖汉, 赵红娟, 孙小淇. 关于可靠性设施布局问题的近似算法[J]. 运筹学学报, 2015, 19(4): 14-24.