摘要
圈问题是图论、组合优化、运筹学、数理经济学以及理论计算机科学中的重要研究对象。本文的研究围绕旅行商问题和最大覆盖圈包装问题展开。作为最经典的圈问题之一，旅行商问题关注图上经过每个顶点一次且仅一次的最短圈。该问题可嵌入几何空间，成为一个几何化的组合优化问题。最大覆盖圈包装问题则在实际生活中有重要应用价值。其优化目标是找到一组总长度最大的顶点不交(边不交)圈。
本文关于旅行商问题的研究关注其在曲面距离空间内的性质，而对最大覆盖圈包装问题则以其子问题——制服调换问题及变异问题——肾脏调换问题为主要研究对象。主要内容如下：
1.在一般的距离空间内，旅行商问题仅存在近似比为常数的近似算法。而在欧氏空间内，该问题存在多项式时间近似方案。其近似方案所使用的“递归剖分+动态规划”的方法已成功应用到一系列的组合优化问题。为探索导致旅行商问题可近似性巨大变化的具体原因，也为进一步拓展“递归剖分+动态规划”方法的适用范围，研究曲面上的旅行商问题。首先证明了球面不可递归正则剖分，表明平面上的算法过程无法直接应用到球面上。接着利用球面与其内接平面之间射影的有限形变特征，将球面旅行商问题实例射影到平面，递归剖分之后连同剖分网格再次射影到球面，在球面上进行动态规划，从而得到了球面旅行商问题的多项式时间近似方案。最后将上述结论推广到一大类曲面上。
2. BHH定理表明随机旅行商问题存在一个重要特征：旅行商问题常数。其直觉基础是均匀随机旅行商问题最优环游的自相似性。球面的对称性较平面更加完美，因此尝试证明球面旅行商问题常数的存在性。BHH定理的现有证明均依赖于欧氏空间的可线性缩放性，而球面无此性质。文中构造了一族渐次逼近球面的球内接多面体，证明了每个此类多面体的表面上旅行商问题常数存在且与平面旅行商问题常数相等，继而取极限将该结论拓展到球面及一些其它曲面。
3.作为最大覆盖圈包装问题的一个子问题，以物易物制服调换问题继承了其O(n3)时间可解性。通过将需要同型号制服且持有同型号制服的人看作一个等价类的方法，将最大覆盖圈包装转化为常量阶有向图上的顶点容量约束整值最大环流，从而得到了以物易物制服调换问题的一个Θ(n)时间算法。最大环流可行域整性的证明进一步增强了该算法的实用性。
4.为进一步缓解待移植肾脏严重短缺的状况，将肾脏调换问题的博弈模型推广到多捐赠者情形。分析了多捐赠者肾脏调换博弈可行解及稳定解的结构，证明了无法以同时捐赠多颗肾脏来换取参与稳定调换，将TTC算法、肾脏调换博弈稳定解的NP难解性以及最大覆盖稳定解的不可近似性拓展到新模型。实验表明这一推广可有效提高病人得到匹配肾脏的可能性。
Cycle problems are important research objects in graph theory, combinatorial opti-mization, operations research, mathematical economics and theoretical computer science.Thisresearchisaboutthetravelingsalesmanproblem(TSP)andthemaximumcovercyclepacking problem (MCCP). In TSP, we concern about the shortest cycle passing througheach vertex exact once. TSP can be embedded into a geometry space, thus becomes ageometric combinatorial optimization problem. MCCP is of great practical value. It’sobjective is to find a set of vertex disjoint (edge disjoint) cycles with the longest totallength.
For TSP, we study its properties in metric spaces defined in curved surfaces. As forMCCP, we focus on a subproblem—the barter uniform exchange problem (BUE) and avariant problem—the kidney exchange problem (KE). The main results are as follows:
1. In a general metric space, TSP has only an approximation algorithm with a constantapproximation ratio. But in an Euclidean space, TSP is in PTAS. The “RecursivePartition+Dynamic Programming” method used in this PTAS has been applied toa series of combinatorial problems successfully. To investigate the reason causingthe great change in the approximability of TSP, and also extend the PTAS’s appli-cation area further, we study TSP in curved surfaces. First, we prove that a spheresurface has no recursively regular partitions, which means the plane algorithm cannot be used in the sphere surface without change. Thanks to the finiteness of thedeformation of the spherical projection between the sphere surface and any sphereinscribed plane, we project the spherical TSP instance onto the plane, recursive-ly partition it, and then project it back onto the sphere surface with the partitiongrid. Next, we perform dynamic programming on the sphere surface, and get thePTAS for the spherical TSP. Last, we extend this result to TSP in a class of curvedsurfaces.
2. BHH theorem shows an important characteristic of random TSP: the TSP constant.Theintuitionbehindistheself-similarityoftheoptimaltourfortheuniformrandomTSP. The sphere surface has a more perfect symmetry than the plane. So we try toprovetheexistenceofasphericalTSPconstant. TheproofsofBHHtheoremknownalready all rely on the linear scalability of Euclidean spaces. Curved surfaces don’t possess this feature. A set of sphere inscribed polyhedra whose surfaces approxi-mate to the sphere surface monotonously were constructed. It’s proved that eachsuch surface has a TSP constant and all these constants are equal to the plane TSPconstant. This result was generalized to the sphere surface by limitation and thento some other curved surfaces.
3. As a subproblem of MCCP, BUE inherits the O(n3) time solvability. By takingpeoplewantingthesametypeofuniformandholdingthesametypeofuniformasanequivalence class, transform BUE into a vertex constraint integer value maximumcirculation problem on a constant order digraph, which give us a Θ(n) algorithm forBUE. The proof of the feasible region for the maximum circulation boosts up thepracticality of the algorithm further.
4. To alleviate the serious shortage of kidneys for transplanting further, generalize thegame model of KE to the case that one patient may have multiple donors. Analyzethe structures of the feasible solutions and the stable solutions to the new game,prove that donating multiple kidneys at the same time is of no help in getting intoa stable exchange, and extend the TTC algorithm, the NP-hardness of finding astable solution and the inapproximability of finding a maximum covering stablesolution to the new model. Experiments show that this generalization increases theprobability that a patient gets a matched kidney.
引文
[1] Goldreich O. Computational Complexity: A Conceptual Perspective [M]. Cam-bridge University Press,2008.
[2] Arora S, Barak B. Computational Complexity: A Morden Approach [M]. Cam-bridge University Press,2009.
[3] Gutin G, Punnen A P. The Traveling Salesman Problem and Its Variations [M].Kluwer Academic Publishers,2004.
[4] KarpR.Probabilisticanalysisofpartitioningalgorithmsforthetraveling-salesmanproblem in the plane [J]. Mathematics of Operations Research.1977,2(3):209–224.
[5] B ckenhauer H, Hromkovic J, Kneis J, et al. The Parameterized Approximabilityof TSP with Deadlines [J]. Theory of Computing Systems.2007,41(3):431–444.
[6] Garey M R, Johnson D S. Computers and Intractability: A Guide to the Theory ofNP-completeness [M]. W. H. Freeman,1979.
[7] Crescenzi P, Kann V. A compendium of NP optimization problems [EB/OL].http://www.nada.kth.se//～viggo/problemlist/index.html.2012.
[8] List of NP-complete Problems [EB/OL]. http://en.vikipedia.org/wiki/List-of-NP-complete-problems.2012.
[9] Graham R L. Bounds for certain multiprocessing anomalies [J]. Bell System Tech-nical Journal.1966,45(9):1563–1581.
[10] Garey M R, Graham R L, Ullman J D. Worst case analysis of memory allocationalgorithms [C]. In Proceedings of the4th Annual ACM Symposium on Theory ofComputing.1972:143–150.
[11] Johnson D S. Approximation algorithms for combinatorial problems [J]. Journalof Computer and System Sciences.1974,9(3):256–278.
[12] Alon N, Shapira A, Sudakov B. Additive approximation for edge-deletion prob-lems [J]. Annals of Mathematics.2009,170(1):371–411.
[13] Hochbaum D. Approximation Algorithms for NP-hard Problems [M]. PWS Pub-lishing,1996.
[14] Vazirani V V. Approximation Algorithms [M]. Springer,2001.
[15] Gonzalez T F. Handbook of Approximation Algorithms and Metaheuristics [M].Chapman&Hall/CRC,2007.
[16] Williamson D P, Shmoys D B. The Design of Approximation Algorithms [M].Cambridge University Press,2010.
[17]堵丁柱,葛可一,胡晓东.近似算法的设计与分析[M].北京:高等教育出版社,2011.
[18] Mayer E W, Pr mel H J, Steger A. Lectures on Proof Verification and Approxi-mation Algorithms [M]. Springer,1998.
[19] Ausiello G, Crescenzi P, Kann G G V, et al. Complexity and Approximation:Combinatorial Optimization Problems and Their Approximability Properties [M].Springer,1999.
[20] Goemans M. Semidefinite programming in combinatorial optimization [J]. Math-ematical Programming.1997,79(1):143–161.
[21] LovászL.Semidefiniteprogramsandcombinatorialoptimization[M]//ReedBA,Sales C L. In Recent Advances in Algorithms and Combinatorics. Springer,2003:137–194.
[22] AroraS,BollobasB,LovaszL.Provingintegralitygapswithoutknowingthelinearprogram[C].InProceedingsofthe43rdAnnualIEEESymposiumonFoundationsof Computer Science.2002:313–322.
[23] Ladner R. On the structure of polynomial time reductibility [J]. Journal of theACM.1975,22(1):155–171.
[24] Johnson D S. The NP-complete column: the many limits on approximation [J].ACM Transactions on Algorithms.2006,2(3):473–489.
[25] Trevisan L. Reductions and (Non-)Approximability [D]. Italy: Università DegliStudi Di Roma,1997.
[26] GareyMR,JohnsonDS.“Strong”NPcompletenessresults:motivation,examplesand implications [J]. Journal of the ACM.1978,25(3):499–508.
[27] Papadimitriou C, Yannakakis M. Optimization, approximation and complexityclasses [J]. Journal of Computer and System Sciences.1991,43(3):425–440.
[28] Fagin R. Generalized first-order spectra and polynomial-time recognizable set-s [M]//Karp R. In Complexity of Computer Computations. AMS,1974:43–73.
[29] AroraS,SafraS.Probabilisticcheckingofproofs:anewcharacterizationofNP[J].Journal of the ACM.1998,45(1):70–122.
[30] Arora S, Lund C, Motwani R, et al. Proof verification and hardness of approxima-tion problems [J]. Journal of the ACM.1998,45(3):501–555.
[31] Arora S. Probabilistic checking of proofs and hardness of approximation problem-s [D]. USA: University of California at Berkeley,1995.
[32] Sudan M. Efficient checking of polynomials and proofs and the hardness of ap-proximation problems [D]. USA: University of California at Berkeley,1995.
[33] Dinur I. The PCP theorem by gap amplification [J]. Journal of the ACM.2007,54(3):1–44.
[34] Radhakrishnan J, Sudan M. On Dinur’s proof of the PCP theorem [J]. Bulletin ofthe American Mathematical Society.2007,44(1):19–61.
[35] H stad J. Some optimal inapproximability results [J]. Journal of the ACM.2001,48(4):798–859.
[36] Moshkovitz D, Raz R. Two-query PCP with subconstant error [J]. Journal of theACM.2010,57(5):1–29.
[37] Sudan M. Probabilistically checkable proofs [J]. Communication of the ACM.2009,52(3):76–85.
[38] H stad J. Clique is hard to approximate within n to the power1[J]. Acta Math-ematica.1999,182(1):105–142.
[39] Feige U. A threshold of lnn for approximating set cover [J]. Journal of the ACM.1998,45(4):634–652.
[40] Khot S. On the power of unique2-prover1-round games [C]. In Proceedings ofthe34th Annual ACM Symposium on Theory of Computing.2002:767–775.
[41] Khot S, Regev O. Vertex cover might be hard to approximate to within2[J].Journal of Computer and System Sciences.2008,74(3):335–349.
[42] Khot S, Kindler G, Mossel E, et al. Optimal inapproximability results for MAX-CUT and other2-variable CSPs?[J]. SIAM Journal on Computing.2007,37(1):319–357.
[43] GuruswamiV,ManokaranR,RaghavendraP.Beatingtherandomorderingishard:inapproximability of maximum acyclic subgraph [C]. In Proceedings of the49thAnnual IEEE Symposium on Foundations of Computer Science.2008:573–582.
[44] Raghavendra P. Optimal algorithms and inapproximability results for every C-SP?[C]. In Proceedings of the40th Annual ACM Symposium on Theory of Com-puting.2008:245–254.
[45] Raghavendra P, Steurer D. How to round any CSP [C]. In Proceedings of the50thAnnual IEEE Symposium on Foundations of Computer Science.2009:586–594.
[46] Raghavendra P, Steurer D. Integrality gaps for strong SDP relaxations of uniquegames [C]. In Proceedings of the50th Annual IEEE Symposium on Foundationsof Computer Science.2009:575–585.
[47] Raghavendra P. Approximating NP-hard problems efficient algorithms and theirlimits [D]. USA: University of Washington,2009.
[48] Halperin E. Improved approximation algorithms for the vertex cover problemin graphs and hypergraphs [J]. SIAM Journal on Computing.2002,31(5):1608–1623.
[49] SahniS,GonzalezT.P-completeapproximationproblems[J].JournaloftheACM.1976,23(3):555–565.
[50] Paluch K, Mucha M, Madry A. A7/9-approximation algorithm for the maxi-mum traveling salesman problem [M]//Dinur I. In Approximation, Random-ization, and Combinatorial Optimization: Algorithms and Techniques. Springer,2009:298–311.
[51] Ausiello G, D’Atri A, Protasi M. On the structure of combinatorial problemsand structure preserving reductions [C]. In Proceedings of the4th InternationalColliquium on Automata, Language and Programming.1977:45–60.
[52] ZemelE.Measuringthequalityofapproximatesolutionstozero-oneprogrammingproblems [J]. Mathematics of Operations Research.1981,6(3):319–332.
[53] Demange M, Paschos V T. On an approximation measure founded on the linksbetween optimization and polynomial approximation theory [J]. Theoretical Com-puter Science.1996,158:117–141.
[54] Hassin R, Khuller S. Z-approximations [J]. Journal of Algorithms.2001,41(2):429–442.
[55] MonnotJ.Differentialapproximationresultsforthetravelingsalesmanandrelatedproblems [J]. Information Processing Letters.2002,82(5):229–235.
[56] Orponen P, Mannila H. On approximation preserving reductions: complete prob-lems and robust measures, C-1987-28[R].1987.
[57] AusielloG,BazganC,Demange M,etal.Completenessindifferentialapproxima-tion classes [J]. International Journal of Foundations of Computer Science.2005,16(6):1267–1276.
[58] Bazgan C, Paschos V T. Differential approximation for optimal satisfiability andrelated problems [J]. European Journal of Operational Research.2003,147(2):397–404.
[59] Bazgan C, Escoffier B, Paschos V T. Completeness in standard and differentialapproximationclasses: poly-(D)APXand(D)PTAS-completeness[J].TheoreticalComputer Science.2005,339(2):272–292.
[60] Escoffier B, Paschos V T. Differential approximation of MIN SAT, MAX SAT andrelated problems [J]. European Journal of Operational Research.2007,181(2):620–633.
[61] Applegate D L, Bixby R E, Chvatal V, et al. The Traveling Salesman Problem: AComputational Study [M]. Princeton University Press,2006.
[62] Chandra B, Karloff H, Tovey C. New results on the old k-opt algorithm for theTSP [C]. In Proceedings of the5th Annual ACM-SIAM Symposium on DiscreteAlgorithms.1994:150–159.
[63] Punnen A, Margot F, Kabadi S. TSP heuristics: domination analysis and complex-ity [J]. Algorithmica.2003,35(2):111–127.
[64] Bendall G, Margot F. Greedy-type resistance of combinatorial problems [J]. Dis-crete Optimization.2006,3(4):288–298.
[65]赖虹建.拟阵论[M].北京:高等教育出版社,2002:314–319.
[66] Gutin G, Yeo A. Anti-matroids [J]. Operations Research Letters.2002,30(2):97–99.
[67] Rublineckii V. Estimates of the accuracy of procedures in the traveling salesmanproblem [J]. Numerical Mathematics and Computer Technology.1973,4:18–23.
[68] SarvanovV.Themeanvalueofthefunctionaloftheassignmentproblem[J].VestsiAkad Navuk BSSR, Ser Fiz-Mat Navuk.1976,143(2):111–114.
[69] Gutin G, Yeo A. Polynomial approximation algorithms for the TSP and the QAPwith a factorial domination number [J]. Discrete Applied Mathematics.2002,119(1-2):107–116.
[70] Gutin G, Goldengorin B, Huang J. Worst case analysis of max-regret, greedy andother heuristics for multidimensional assignment and traveling salesman problem-s [J]. Journal of Heuristics.2008,14(2):169–181.
[71] Gutin G, Karapetyan D. Local search heuristics for the multidimensional assign-ment problem [M]//Lipshteyn M, Levit V, McConnell R. In Graph Theory, Com-putational Intelligence and Thought. Springer,2009:100–115.
[72] Gutin G, Yeo A. TSP tour domination and Hamilton cycle decompositions of reg-ular digraphs [J]. Operations Research Letters.2001,28(3):107–111.
[73] Alon N, Gutin G, Krivelevich M. Algorithms with large domination ratio [J]. Jour-nal of Algorithms.2004,50(1):118–131.
[74] Gutin G, Koller A, Yeo A. Note on upper bounds for TSP domination number [J].Algorithmic Operation Research.2006,1(1):52–54.
[75] Bendall G L. Domination analysis beyond the TSP [D]. USA: University of Ken-tucky,2004.
[76] Gutin G. Domination analysis in combinatorial optimization [M]//Floudas C A,Pardalos P M. In Encyclopedia of Optimization.2nd ed. Springer,2009.
[77] Lawler E L, Lenstra J K, Kan A H G R, et al. The Travelling Salesman Problem:A Guided Tour of Combinatorial Optimization [M]. Wiley,1985.
[78] Reinelt G. The Traveling Salesman: Computational Solutions for TSP Applica-tions [M]. Springer,1994.
[79] Cook W J. In Pursuit of the Traveling Salesman [M]. Princeton University Press,2012.
[80] Edmonds J. Optimum branchings [J]. Journal of Research National Bureau of S-tandards, Part B.1966,17B (4):233–240.
[81] Karp R M. Reducibility among combinatorial problems [M]//Jünger M,Liebling T M, Naddef D, et al. In50Years of Integer Programming1958-2008.Springer,2010:219–241.
[82] Held M, Karp R. A dynamic programming approach to sequencing problem-s [J]. Journal of the Society for Industrial and Applied Mathematics.1962,10(1):196–210.
[83] Garey M R, Graham R L, Johnson D S. Some NP-complete geometric problem-s [C]. In Proceedings of the8th Annual ACM Symposium on Theory of Comput-ing.1976:10–22.
[84] Papadimitriou C H. The Euclidean travelling salesman problem is NP-complete [J]. Theoretical Computer Science.1977,4(3):237–244.
[85] Christofides N. Worst-case analysis of a new heuristic for the travelling salesmanproblem,388[R].1976.
[86] PapadimitriouCH,YannakakisM.Thetravelingsalesmanproblemwithdistancesone and two [J]. Mathematics of Operations Research.1993,18(1):1–11.
[87] Papadimitriou C H, Vempala S. On the approximability of the traveling salesmanproblem [J]. Combinatorica.2006,26(1):101–120.
[88] Berman P, Karpinski M.8/7-approximation algorithm for (1,2)-TSP [C]. In Pro-ceedings of the17th Annual ACM-SIAM Symposium on Discrete Algorithm.2006:648–665.
[89] Engebretsen L, Karpinski M. TSP with bounded metrics [J]. Journal of Computerand System Sciences.2006,72(4):509–546.
[90] B ckenhauer H, Seibert S. Improved lower bounds on the approximability of thetraveling salesman problem [J]. Theoretical Informatics and Applications.2000,34(3):213–255.
[91] HwangRZ,ChangRC,LeeRCT.Thesearchingoverseparatorsstrategytosolvesome NP-hard problems in subexponential time [J]. Algorithmica.1993,9(4):398–423.
[92] Smith W D. Finding the optimum N-city traveling salesman tour in the Euclideanplane in subexponential time and polynomial space [Z].1988. manuscript.
[93] GrigniM,KoutsoupiasE,PapadimitriouCH.Anapproximationschemeforplanargraph TSP [C]. In Proceedings of the36th Annual IEEE Symposium on Founda-tions of Computer Science.1995:640–645.
[94] Arora S. Polynomial time approximation schemes for Euclidean traveling sales-man and other geometric problems [C]. In Proceedings of the37th Annual Sym-posium IEEE on Foundations of Computer Science.1996:2–12.
[95] MitchellJSB.Guillotinesubdivisionsapproximatepolygonalsubdivisions:asim-ple polynomial-time approximation scheme for geometric k-MST problem [C]. InProceedings of the7th Annual ACM-SIAM Symposium on Discrete Algorithms.1996:402–408.
[96] Arora S. Nearly linear time approximation schemes for Euclidean TSP and othergeometric problems [C]. In Proceedings of the38th Annual IEEE Symposium onFoundations of Computer Science.1997:554–563.
[97] RaoSB,SmithWD.Improvedapproximationschemesforgeometricalgraphsviaspanners and banyans [C]. In Proceedings of the30th Annual ACM Symposiumon Theory of Computing.1998:540–550.
[98] Trevisan L. When Hamming meets Euclid: the approximability of geometric TSPand MST [C]. In Proceedings of the29th Annual ACM Symposium on Theory ofComputing.1997:21–29.
[99] Perl Y, Shiloach Y. Finding two disjoint paths between two pairs of vertices in agraph [J]. Journal of the ACM.1978,25(1):1–9.
[100] SchrijverA.CombinatorialOptimization:PolyhedraandEfficiency[M].Springer,2003.
[101] Thomas R, Wollan P. An improved linear edge bound for graph linkages [J]. Eu-ropean Journal of Combinatorics.2005,26(3-4):309–324.
[102] Seymour P. Disjoint paths in graphs [J]. Discrete Mathematics.1980,29(3):293–309.
[103] Thomassen C.2-linked graphs [J]. European Journal of Combinatorics.1980,1:371–378.
[104] Even S, Itai A, Shamir A. On the complexity of time table and multicommodityflow problems [J]. SIAM Journal on Computing.1976,5(4):691–703.
[105] Lynch J F. The equivalence of theorem proving and the interconnection prob-lem [J]. SIGDA Newsletter.1975,5(3):31–36.
[106] Kramer M E, van Leeuwen J. The complexity of wire routing and finding the min-imum area layouts for arbitrary VLSI circuits [M]//Preparata F P. In Advances inComputing Research: VLSI Theory. London: JAI Press,1984:129–146.
[107] Middendorf M, Pfeiffer F. On the complexity of the disjoint paths problem [J].Combinatorica.1993,13(1):97–107.
[108] Erlebach T, Jansen K. The maximum edge-disjoint paths problem in bidirectedtrees [J]. SIAM Journal on Discrete Mathematics.2001,14(3):326–355.
[109] Garg N, Vazirani V V, Yannakakis M. Primal-dual approximation algorithms forintegral flow and multicut in trees [J]. Algorithmica.1997,18(1):3–20.
[110] Srinivasan A. Improved approximations for edge-disjoint paths, unsplittable flow,and related routing problems [C]. In Proceedings of the38th Annual IEEE Sym-posium on Foundations of Computer Science.1997:416–425.
[111] Kolliopoulos S G, Stein C. Approximating disjoint-path problems using packinginteger programs [J]. Mathematical Programming.2004,99(1):63–87.
[112] AndrewsM,ZhangL.Hardnessoftheundirectededge-disjointpathsproblem[C].In Proceedings of the37th Annual ACM Symposium on Theory of Computing.2005:276–283.
[113] Trevisan L. Non-approximability results for optimization problems on boundeddegree instances [C]. In Proceedings of the33rd Annual ACM Symposium onTheory of Computing.2001:453–461.
[114] Samorodnitsky A, Trevisan L. A PCP characterization of NP with optimal amor-tized query complexity [C]. In Proceedings of the32nd Annual ACM Symposiumon Theory of Computing.2000:191–199.
[115] Andrews M, Chuzhoy J, Sanjeev K, et al. Hardness of the undirected edge-disjointpaths problem with congestion [C]. In Proceedings of the46th Annual IEEE Sym-posium on Foundations of Computer Science.2005:226–241.
[116] Andrews M, Chuzhoy J, Guruswami V, et al. Inapproximability of edge-disjointpaths and low congestion routing on undirected graphs [J]. Combinatorica.2010,30(5):485–520.
[117] Chuzhoy J, Khanna S. New hardness results for undirected edge disjoint paths [Z].2005. manuscript.
[118] Chekuri C, Khanna S, Shepherd F B. An O(√n) approximation and integralitygap for disjoint paths and unsplittable flow [J]. Theory of Computing.2006,2:137–146.
[119] Nguyen T. On the disjoint paths problem [J]. Operations Research Letters.2007,35(1):10–16.
[120] Guruswami V, Khanna S, Rajaraman R, et al. Near-optimal hardness results andapproximation algorithms for edge-disjoint paths and related problems [J]. Journalof Computer and System Sciences.2003,67(3):473–496.
[121] Ma B, Wang L. On the inapproximability of disjoint paths and minimum Steinerforest with bandwidth constraints [J]. Journal of Computer and System Sciences.2000,60(1):1–12.
[122] Chekuri C, Khanna S. Edge-disjoint paths revisited [J]. ACM Transactions on Al-gorithms.2007,3(4):46:1–46:18.
[123] Varadarajan K, Venkataraman G. Graph decomposition and a greedy algorithm foredge-disjoint paths [C]. In Proceedings of the15th Annual ACM-SIAM Sympo-sium on Discrete Algorithms.2004:379–380.
[124]谢政,张晓明,陈挚.寻找最大带宽的独立路径对算法[J].国防科技大学学报.2012,34(5):158–163.
[125] ShiloachY.Apolynomialsolutiontotheundirectedtwopathsproblem[J].Journalof the ACM.1980,27(3):445–456.
[126] Robertson N, Seymour P D. Graph minors. XIII. The disjoint paths problem [J].Journal of Combinatorial Theory, Series B.1995,63(1):65–110.
[127] Bienstock D, Langston M A. Algorithmic implications of the graph minor theo-rem [M]//Ball M O, Magnanti T L, Monma C L, et al. In Handbooks in Opera-tionsResearchandManagementScience,7:NetworkModels.Amsterdam:North-Holland,1995.
[128] Kawarabayashi K, Kobayashi Y, Reed B. The disjoint paths problem in quadratictime [EB/OL]. http://research.nii.ac.jp/～k_keniti/quaddp1.pdf,2012.
[129] Fortune S, Hopcroft J, Wyllie J. The directed subgraph homeomorphism prob-lem [J]. Theoretical Computer Science.1980,10(2):111–121.
[130] Thomassen C. Highly connected non-2-linked digraphs [J]. Combinatorica.1991,11(4):393–395.
[131] Kleinberg J. Approximation Algorithms for Disjoint Paths Problems [D]. USA:MIT,1996.
[132] HarshaP,CharikarM.Limitsofapproximationalgorithms:PCPanduniquegames
[EB/OL]. http://dimacs.rutgers.edu/Workshops/Limits/.2012.
[133] Bafna V, Pevzner P A. Genome rearrangements and sorting by reversals [J]. SIAMJournal on Computing.1996,25:272–289.
[134] Balister P. Packing digraphs with directed closed trails [J]. Combinatorics, Proba-bility and Computing.2003,12(1):1–15.
[135] Bang-Jensen J, Gutin G. Digraphs Theory, Algorithms and Applications [M].2nded. Springer,2009.
[136] Kunzmann A, Wunderlich H J. An analytical approach to the partial scan prob-lem [J]. Journal of Electronic Testing.1990,1(2):163–174.
[137] Erd s P, Pósa L. On the independent circuits contained in a graph [J]. CanadianJournal of Mathematics.1965,17:347–352.
[138] Younger D H. Graphs with interlinked directed circuits [C]. In Proceedings of theMidwest Symposium on Circuit Theory2.1973: XVI2.1–XVI2.7.
[139] Bermond J C, Thomassen C. Cycles in digraphs-A survey [J]. Journal of GraphTheory.1981,5(1):1–43.
[140] Thomassen C. Girth in graphs [J]. Journal of Combinatorial Theory, Series B.1983,35(2):129–141.
[141] Alon N. Disjoint directed cycles [J]. Journal of Combinatorial Theory, Series B.1996,68(2):167–178.
[142] PapadimitriouCH,YannakakisM.Onlimitednondeterminismandthecomplexityof the V-C dimension [J]. Journal of Computer and System Sciences.1996,53(2):161–170.
[143] Alon N, Yuster R, Zwick U. Color-coding [J]. Journal of the ACM.1995,42(4):844–856.
[144] Hassin R, Rubinstein S. An approximation algorithm for maximum triangle pack-ing [J]. Discrete Applied Mathematics.2006,154(6):971–979.
[145] Hassin R, Rubinstein S. Erratum to an approximation algorithm for maximum tri-angle packing [J]. Discrete Applied Mathematics.2006,154(6):971–979.
[146] Kann V. Maximum bounded3-dimensional matching is MAX SNP-complete [J].Information Processing Letters.1991,37(1):27–35.
[147] Holyer I. The NP-completeness of some edge-partition problems [J]. SIAM Jour-nal on Computing.1981,10(4):713–717.
[148] Caprara A, Rizzi R. Packing triangles in bounded degree graphs [J]. InformationProcessing Letters.2002,84(4):175–180.
[149] Rautenbach D, Regen F. On packing shortest cycles in graphs [J]. InformationProcessing Letters.2009,109(14):816–821.
[150] Lucchesi C. A Minimax Equality for Directed Graphs [D]. Canada: University ofWaterloo,1976.
[151] Caprara A, Panconesi A, Rizzi R. Packing cycles in undirected graphs [J]. Journalof Algorithms.2003,48(1):239–256.
[152] Krivelevich M, Nutov Z, Salavatipour M R, et al. Approximation algorithms andhardnessresultsforcyclepackingproblems[J].ACMTransactionsonAlgorithms.2007,3(4):48.
[153] Friggstad Z, Salavatipour M. Approximability of packing disjoint cycles [J]. Al-gorithmica.2011,60(2):395–400.
[154] Lingas A, Lundell E-M. Efficient approximation algorithms for shortest cycles inundirected graphs [J]. Information Processing Letters.2009,109(10):493–498.
[155]张少强,王继强,李曙光.几类特殊平面图的圈包装问题[J].山东大学学报.2004,39(1):1–4.
[156] Lewis J M, Yannakakis M. The node-deletion problem for hereditary propertiesis NP-complete [J]. Journal of Computer and System Sciences.1980,20(2):219–230.
[157] Yannakakis M. Edge-deletion problems [J]. SIAM Journal on Computing.1981,10(2):297–309.
[158] Asano T. An application of duality to edge-deletion problems [J]. SIAM Journalon Computing.1987,16(2):312–331.
[159] Golumbic M C, Kaplan H, Shamir R. On the complexity of DNA physical map-ping [J]. Advances in Applied Mathematics.1994,15(3):251–261.
[160] Rose D J. A graph-theoretic study of the numerical solution of sparse positive def-inite systems of linear equations [M]//Read R. In Graph Theory and Computing.Academic Press,1972:183–217.
[161] Chen Z-Z, Fellows M, Fu B, et al. A linear kernel for co-path/cycle pack-ing [M]//Chen B. In Algorithmic Aspects in Information and Management.Springer,2010:90–102.
[162] Digraphs Theory A, Applications.2nd ed. Springer,2009:177–179.
[163] Micali S, Vazirani V V. An O(√|V|·|E|) algorithm for finding maximum matchingin general graphs [C]. In Proceedings of the21st Annual IEEE Symposium onFoundations of Computer Science.1980:17–27.
[164] Gutin G. Finding a longest path in a complete multipartite digraph [J]. SIAM Jour-nal on Discrete Mathematics.1993,6(2):270–273.
[165] Burkard R, Dell’Amico M, Martello S. Assignment Problems [M]. SIAM,2009:128.
[166] Abraham D J, Blum A, Sandholm T. Clearing algorithms for barter exchange mar-kets: enabling nationwide kidney exchanges [C]. In Proceedings of the8th ACMConference on Electronic Commerce.2007:295–304.
[167] Biró P, Manlove D F, Rizzi R. Maximum weight cycle packing in optimal kidneyexchangeprograms[J].DiscreteMathematics,AlgorithmsandApplications.2009,1(4):499–517.
[168] Arkin E M, Hassin R. On local search for weighted k-set packing [J]. Mathmaticsof Operation Research.1998,23(3):640–648.
[169] Berman P. A d/2approximation for maximum weight independent set in d-clawfree graphs [C]. In Proceedings of the7th Scandinavian Workshop on AlgorithmerTheory.2000:214–219.
[170] Arora S. Polynomial time approximation schemes for Euclidean traveling sales-manandothergeometricproblems[J].JournaloftheACM.1998,45(5):753–782.
[171] Arora S, Raghavan P, Rao S. Approximation schemes for Euclidean k-mediansand related problems [C]. In Proceedings of the30th Annual ACM Symposium onTheory of Computing.1998:106–113.
[172] Arora S, Karakostas G. Approximation schemes for minimum latency problem-s [J]. SIAM Journal on Computing.2003,32(5):1317–1337.
[173] Kolliopoulos S G, Rao S. A nearly linear-time approximation scheme for theEuclidean k-median problem [J]. SIAM Journal on Computing.2006,37(3):757–782.
[174] Czumaj A, Lingas A. A polynomial time approximation scheme for Euclideanminimum cost k-connectivity [C]. In Proceedings of the25th Annual InternationalColloquium on Automata, Language and Programming.1998:682–694.
[175] Czumaj A, Lingas A. On approximability of the minimum-cost k-connected s-panning subgraph problem [C]. In Proceedings of the10th Annual ACM-SIAMSymposium on Discrete Algorithms.1999:281–290.
[176] Czumaj A, Lingas A. Fast approximation schemes for Euclidean multi-connectivity problems [C]. In Proceedings of the27th Annual International Col-loquium on Automata, Language and Programming.2000:856–868.
[177] Arora S. Approximation schemes for NP-hard geometric optimization problems:a survey [J]. Mathematical Programming.2003,97(1-2):43–69.
[178] Arora S, Chang K. Approximation schemes for degree-restricted MST and red-blue separation problems [J]. Algorithmica.2004,40(3):189–210.
[179] Borradaile G, Kenyon-Mathieu C, Klein P. A polynomial-time approximationscheme for Steiner tree in planar graphs [C]. In Proceedings of the18th Annu-al ACM-SIAM Symposium on Discrete Algorithms.2007:1285–1294.
[180] Borradaile G, Kenyon-Mathieu C, Klein P. Steiner tree in planar graphs: anO(n log(n)) approximation scheme with singly-exponential dependence on ep-silon[C].InProceedingsofthe10thWorkshoponAlgorithmsandDataStructures.2007:275–286.
[181] Tazari S, Müller-Hannemann M. Dealing with large hidden constants: engineeringa planar Steiner tree PTAS [C]. In Proceedings of the3rd Workshop on AlgorithmEngineering and Experimentation.2009.
[182] BorradaileG,KleinPN,MathieuC.Apolynomial-timeapproximationschemeforEuclidean Steiner forest [C]. In Proceedings of the49th Annual IEEE Symposiumon Foundations of Computer Science.2008:115–124.
[183] Remy J, Steger A. Approximation schemes for node-weighted geometric Steinertree problems [J]. Algorithmica.2009,55(1):240–267.
[184] Remy J, Steger A. A quasi-polynomial time approximation scheme for minimumweight triangulation [J]. Journal of the ACM.2009,56(3):1–47.
[185] Chen K, Har-Peled S. The orienteering problem in the plane revisited [C]. InProceedings of the22nd Annual Symposium on Computational Geometry.2006:247–254.
[186] Chen K, Har-Peled S. The Euclidean orienteering problem revisited [J]. SIAMJournal on Computing.2008,38(1):385–397.
[187] AsanoT,KatohN,TamakiH,etal.Coveringpointsintheplanebyk-tours:towardsa polynomial time approximation scheme for general k [C]. In Proceedings of the9th Annual ACM-SIAM Symposium on Discrete Algorithms.1997:275–283.
[188] Das A, Mathieu C. A quasi-polynomial time approximation scheme for Euclideancapacitated vehicle routing [C]. In Procedings of the21st Annual ACM-SIAMSymposium on Discrete Algorithms.2010:390–403.
[189] Adamaszek A, Czumaj A, Lingas A. PTAS for k-tour cover problem on the planefor moderately large values of k [M]. In Algorithms and Computation. Springer,2009:994–1003.
[190] Tansini L. Probabilistic and Experimental Analysis of Heuristic Algorithms forthe Multiple-Depot Vehicle-Routing Problem [D]. G teborg, Sweden: ChalmersUniversity of Technology,2006.
[191] RemyJ.ApproximationSchemesforGeometricProblems[D].Zurich:TechnischeUniversit t München,2007.
[192]赵卫中,冯好娣,朱大铭.欧氏空间货郎担问题的一个多项式时间近似方案的改进与实现[J].计算机研究与发展.2007,44(10):1790–1795.
[193] Courant R，Robbins H．什么是数学[M]．上海：复旦大学出版社，2005：244–248．
[194] Preparata F P, Hong S J. Convex hulls of finite sets of points in two and threedimensions [J]. Communication of the ACM.1977,20(2):87–93.
[195] Bondy J A, Murty U S R. Graph Theory [M]. Springer,2008:260.
[196] Toussaint G. Solving geometric problems with the rotating calipers [C]. In Pro-ceedings of IEEE Mediterranean Electrotechnical Conference.1983:1–10.
[197] BrassP,MoserW,PachJ.ResearchProblemsinDiscreteGeometry[M].Springer,2005:162.
[198] Motwani R, Raghaven P. Randomized Algorithms [M]. Cambridge UniversityPress,1995.
[199] Borgwardt K H. The Simplex Method: A Probabilistic Analysis [M]. Springer,1980.
[200] Spielman D A, Teng S H. Smoothed analysis of algorithms: why the simplex al-gorithm usually takes polynomial time [J]. Journal of the ACM.2004,51(3):385–463.
[201] Beardwood J, Halton J H, Hammersley J M. The shortest path through manypoints [C]. In Proceedings of the Cambridge Philosophical Society. London,1959:299–327.
[202] RheeWT.Onthetravellingsalespersonprobleminmanydimensions[J].RandomStructures and Algorithms.1992,3(3):227–233.
[203] Papadimitriou C H. The probabilistic analysis of matching heuristics [C]. In Pro-ceedings of the15th Allerton Conference on Communication, Control, and Com-puting.1978:368–378.
[204] Steele J M. Subadditive Euclidean functionals and non-linear growth in geometricprobability [J]. The Annais of Probability.1981,9:365–376.
[205] Goemans M, Bertsimas D. Probabilistic analysis of the Held-Karp relaxation forthe Euclidean traveling salesman problem [J]. Mathematics of Operations Re-search.1991,16(1):72–89.
[206] Baltz A, Dubhashi D, Srivastav A, et al. Probabilistic analysis for a multiple depotvehicle routing problem [J]. Random Structures and Algorithms.2007,30(1-2):206–225.
[207] Bompadre A, Dror M, Orlin J B. Probabilistic analysis of unit demand vehiclerounting problems [J]. Journal of Applied Probability.2007,44(1):259–278.
[208] Barthe F, Bordenave C. Combinatorial optimization over two random point sets,1103.2734[R].2011.
[209] Avram F, Bertsimas D. On central limit theorems in geometrical probability [J].The Annals of Applied Probability.1993,3(4):1033–1046.
[210] SteeleJM.ProbabilityTheoryandCombinatorialOptimization[M].SIAM,1997.
[211] YukichJE.ProbabilityTheoryofClassicalEuclideanOptimizationProblems[M].Springer,1998.
[212] Avram F, Bertsimas D. The minimum spanning tree constant in geometrical prob-ability and under the independent model: a unified approach [J]. The Annals ofApplied Probability.1992,2(1):113–130.
[213] McGivney K, Yukich J E. Asymptotics for Voronoi tessellations on random sam-ples [J]. Stochastic Processes and their Applications.1999,83(2):273–288.
[214] Steele J M. Stochastic combinatorial optimizatio from TSPs to MSTs via Cater-pillars and Dogerpillars [EB/OL]. http://www-stat.wharton.upenn.edu/steele/Ac-cessCash/Furman/FurmanSteeleTSPetc.pdf.2012.
[215] Frieze A M. On the value of a random minimum spanning tree problem [J]. Dis-crete Applied Mathematics.1985,10(1):47–56.
[216] SteeleJM.OnFrieze’sζ(3)limitforlengthsofminimalspanningtrees[J].DiscreteApplied Mathematics.1987,18(1):99–103.
[217] Aldous D J. The ζ(2) limit in the random assignment problem [J]. Random Struc-tures Algorithms.2001,18(4):381–418.
[218] Percus A G, Martin O C. Finite size and dimensional dependence in the Euclideantravelingsalesmanproblem[J].PhysicalReviewLetters.1996,76(8):1188–1191.
[219] Johnson D S, McGeoch L A, Rothberg E E. Asymptotic experimental analysis forthe Held-Karp traveling salesman bound [C]. In Proceedings of the7th AnnualACM-SIAM Symposium on Discrete Algorithm.1996:341–350.
[220] Karp R M, Steele J M. Probabilistic analysis of heuristics [M]//Lawler E L,Lenstra J K, Kan A H G R, et al. In The Traveling Salesman Problem: A GuidedTour of Combinatorial Optimization. Wiley,1985:181–205.
[221] Steele J M. Probabilistic and worst case analyses of classical problems of combi-natorial optimization in Euclidean space [J]. Mathematics of Operations Research.1990,15(4):749–770.
[222] Lee S. The central limit theorem for the minimal spanning trees I [J]. The Annalsof Applied Probability.1997,7(4):996–1020.
[223] Lee S. The central limit theorem for the minimal spanning trees II [J]. Advancesin Applied Probability.1999,31(4):969–984.
[224] Penrose M D. The longest edge of the random minimal spanning tree [J]. TheAnnals of Applied Probability.1997,7(2):340–361.
[225] Lee S, Su Z. The central limit theorem for the independence number for minimalspanning trees in the unit square [M]//Barbour A D, Hsiao L, Chen Y. In Stein’sMethod and Applications. World Scientific Publishing Company,2005:103–118.
[226] TSPLIB[EB/OL].http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.2012.
[227] HearnD,BakerMP.ComputerGraphicswithOpenGL[M].3rded.Pearson,2005.
[228] Kirk D. Uniform random rotations [M]//K S. In Graphics Gems III. AcademicPress,1994:126–127.
[229] Military uniform exchange [EB/OL]. http://www.militaryuniformexchange.com/.2012.
[230] Read it swap it [EB/OL]. http://www.readitswapit.co.uk/.2012.
[231] Peerflix [EB/OL]. http://www.peerflix.com/.2012.
[232] Intervac [EB/OL]. http://intervac-online.com/.2012.
[233] National odd shoe exchange [EB/OL]. http://www.oddshoe.org/.2012.
[234] United states renal data system (USRDS)[EB/OL]. http://www.usrds.org/.2012.
[235] Mucha M, Sankowski P. Maximum matchings via Gaussian elimination [C]. InProceedings of the45th Annual IEEE Symposium on Foundations of ComputerScience.2004:248–255.
[236]柳柏濂.组合矩阵论[M].2nd ed.北京:科学出版社,2005:6.
[237] Knuth D E.计算机程序设计艺术：第二卷半数值算法[M].3rd ed.北京:国防工业出版社,2002:107–108.
[238] GLPKforWindows[EB/OL].http://gnuwin32.sourceforge.net/packages/glpk.htm.2012.
[239] Nisan N, Roughgarden T, éva Tardos, et al. Algorithmic Game Theory [M]. Cam-bridge University Press,2007.
[240] The Organ Procurement and Transplantation Network (OPTN)[EB/OL].http://optn.transplant.hrsa.gov/.2012.
[241] Rapaport F T. The case for a living emotionally related international kidney donorexchange registry [J]. Transplantation Proceedings.1986,18:5–9.
[242] Roth A E, S nmez T, ünver M U. Kidney exchange [J]. Quarterly Journal of E-conomics.2004,119(2):457–488.
[243] Cechlárová K, Fleiner T, Manlove D. The kidney exchange game [C]//Zadnik-Stirn L, Drobne S. In Proceedings of the8th International Symposium on Opera-tions Research in Slovenia.2005:77–83.
[244] Cechlárová K, Hajduková J. Stability testing in coalition formationgames [C]//Dupnik V, Zadnik-Stirn L, Drobne S. In Proceedings of the2nd International Symposium on Operations Research in Slovenia.1999:111–116.
[245] Cechlárová K, Romero-Medina A. Stability in coalition formation games [J]. In-ternational Journal of Game Theory.2001,29(4):487–494.
[246] Shapley L, Scarf H. On cores and indivisibility [J]. Journal of Mathematical Eco-nomics.1974,1(1):23–37.
[247] AbrahamD, CechlárováK, Manlove D,et al.Paretooptimality inhouseallocationproblems[M]//DengX,DuD-Z.InAlgorithmsandComputation.Springer,2004:1163–1175.
[248] Cechlárová K, Lacko V. The kidney exchange problem: how hard is it to find adonor?[J]. Annals of Operations Research.2012,193(1):1–17.
[249] Biró P, McDermid E. Three-sided stable matchings with cyclic preferences [J].Algorithmica.2010,58(1):5–18.
[250] Huang C-C. Circular stable matching and3-way kidney transplant [J]. Algorith-mica.2010,58(1):137–150.
[251] Cechlárová K, Hajduková J. Computational complexity of stable partitions withB-preferences [J]. International Journal of Game Theory.2002,31(3):353–364.
[252] Gusfield D, Irving R. The Stable Marriage Problem: Structure and Algorithms,Foundations of Computing [M]. MIT Press,1989.
[253] Irving R W. The cycle roommates problem: a hard case of kidney exchange [J].Information Processing Letters.2007,103(1):1–4.
[254] Biró P, Cechlárová K. Inapproximability of the kidney exchange problem [J]. In-formation Processing Letters.2007,101(5):199–202.
[255] Roth A E. Incentive compatibility in a market with indivisible goods [J]. Eco-nomics Letters.1982,9(2):127–132.
[256] Alcalde-Unzu J, Molis E. Exchange of indivisible goods and indifferences: TheTop Trading Absorbing Sets mechanisms [J]. Games and Economic Behavior.2011,73(1):1–16.
[257] Cook W J, Cunningham W H, Pulleyblank W R, et al.组合优化[M].北京:高等教育出版社,2011:217.
[258] Bollobás B. Extremal Graph Theory [M]. Academic Press,1978.
[259] Halmos P R.朴素集合论[M].北京:世界图书出版公司,2008:54–58.
[260] Knuth D E.计算机程序设计艺术：第一卷基本算法[M].3rd ed.北京:国防工业出版社,2002:102–106.
[261] Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to Algorithms [M].3rded. MIT Press,2009:43–64.
[262] Aaronson S, Kuperberg G, Granade C. The complexity zoo [EB/OL].http://qwiki.stanford.edu/index.php/Compxexity_Zoo.2012.