Research On Algorithms For Two Types Of Cycle Problems

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.