Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs

A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem one can represent such a multigraph as a combination of at most n/sup 2/ cycle covers each taken with an appropriate multiplicity. We prove that if the d-regular multigraph does not contain more than /spl lfloor/d/2/spl rfloor/ copies of any 2-cycle then we can find a similar decomposition into 0(n/sup 2/) pairs of cycle covers where each 2-cycle occurs in at most one component of each pair. Our proof is constructive and gives a polynomial algorithm to find such decomposition. Since our applications only need one such a pair of cycle covers whose weight is at least the average weight of all pairs, we also give a simpler algorithm to extract a single such pair. This combinatorial theorem then comes handy in rounding a fractional solution of an LP relaxation of the maximum and minimum TSP problems. For maximum TSP, we obtain a tour whose weight is at least 2/3 of the weight of the longest tour, improving a previous 5/8 approximation. For minimum TSP we obtain a tour whose weight is at most 0. 842log/sub 2/ n times the optimal, improving a previous 0. 999log/sub 2/ n approximation. Utilizing a reduction from maximum TSP to the shortest superstring problem we obtain a 2. 5-approximation algorithm for the latter problem which is again much simpler than the previous one. Other applications of the rounding procedure are approximation algorithms for maximum 3-cycle cover (factor 2/3, previously 3/5) and maximum asymmetric TSP with triangle inequality (factor 10/13, previously 3/4 ).

Authors

• Haim Kaplan
• Moshe Lewenstein
• Nira Shafrir
• Maxim Sviridenko

Keywords

• Approximation algorithms
• Computer science
• Polynomials
• Traveling salesman problems
• Application software
• Algorithm design and analysis
• Biology computing
• Computer applications
• Computational biology
• Estimation Algorithm
• Multigraph
• Triangle Inequality
• Fractional Solution
• Edge Weights
• Steps Of Algorithm
• Directed Graph
• Even Number
• Cycle Length
• Red Edge
• Power-of-two
• Results Of The Previous Section
• Variant Of Problem
• Regular Graphs
• Decomposition Theorem
• Hamiltonian Path