【作者】 王刚；

【导师】 骆志刚；

【作者基本信息】 国防科学技术大学 ， 计算机科学与技术， 2013， 博士

【摘要】 圈问题是图论、组合优化、运筹学、数理经济学以及理论计算机科学中的重要研究对象。本文的研究围绕旅行商问题和最大覆盖圈包装问题展开。作为最经典的圈问题之一，旅行商问题关注图上经过每个顶点一次且仅一次的最短圈。该问题可嵌入几何空间，成为一个几何化的组合优化问题。最大覆盖圈包装问题则在实际生活中有重要应用价值。其优化目标是找到一组总长度最大的顶点不交(边不交)圈。本文关于旅行商问题的研究关注其在曲面距离空间内的性质，而对最大覆盖圈包装问题则以其子问题——制服调换问题及变异问题——肾脏调换问题为主要研究对象。主要内容如下：1.在一般的距离空间内，旅行商问题仅存在近似比为常数的近似算法。而在欧氏空间内，该问题存在多项式时间近似方案。其近似方案所使用的“递归剖分+动态规划”的方法已成功应用到一系列的组合优化问题。为探索导致旅行商问题可近似性巨大变化的具体原因，也为进一步拓展“递归剖分+动态规划”方法的适用范围，研究曲面上的旅行商问题。首先证明了球面不可递归正则剖分，表明平面上的算法过程无法直接应用到球面上。接着利用球面与其内接平面之间射影的有限形变特征，将球面旅行商问题实例射影到平面，递归剖分之后连同剖分网格再次射影到球面，在球面上进行动态规划，从而得到了球面旅行商问题的多项式时间近似方案。最后将上述结论推广到一大类曲面上。2. BHH定理表明随机旅行商问题存在一个重要特征：旅行商问题常数。其直觉基础是均匀随机旅行商问题最优环游的自相似性。球面的对称性较平面更加完美，因此尝试证明球面旅行商问题常数的存在性。BHH定理的现有证明均依赖于欧氏空间的可线性缩放性，而球面无此性质。文中构造了一族渐次逼近球面的球内接多面体，证明了每个此类多面体的表面上旅行商问题常数存在且与平面旅行商问题常数相等，继而取极限将该结论拓展到球面及一些其它曲面。3.作为最大覆盖圈包装问题的一个子问题，以物易物制服调换问题继承了其O(n3)时间可解性。通过将需要同型号制服且持有同型号制服的人看作一个等价类的方法，将最大覆盖圈包装转化为常量阶有向图上的顶点容量约束整值最大环流，从而得到了以物易物制服调换问题的一个Θ(n)时间算法。最大环流可行域整性的证明进一步增强了该算法的实用性。4.为进一步缓解待移植肾脏严重短缺的状况，将肾脏调换问题的博弈模型推广到多捐赠者情形。分析了多捐赠者肾脏调换博弈可行解及稳定解的结构，证明了无法以同时捐赠多颗肾脏来换取参与稳定调换，将TTC算法、肾脏调换博弈稳定解的NP难解性以及最大覆盖稳定解的不可近似性拓展到新模型。实验表明这一推广可有效提高病人得到匹配肾脏的可能性。更多还原

【Abstract】 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.更多还原