Long Tours and Short Superstrings (Preliminary Version)

This paper considers weight-maximizing variants of the classical symmetric and asymmetric traveling-salesman problems. Like their weight-minimizing counterparts, these variants are MAX SNP-hard. We present the first nontrivial approximation algorithms for these problems. Our algorithm for directed graphs finds a tour whose weight is at least 38/63/spl ap/0. 603 times the weight of a maximum-weight tour, and our algorithm for undirected graphs finds a tour whose weight is at least 5/7/spl ap/0. 714 times optimal. These bounds compare favorably with the 1/2 and 2/3 bounds that can be obtained for undirected and directed graphs, respectively, by simply deleting the minimum-weight edge from each cycle of a maximum-weight cycle cover. Our algorithm for directed graphs can be used to improve several recent approximation results for the shortest-superstring problem. >

Authors

• S. Rao Kosaraju
• James K. Park
• Cliff Stein 0001

Keywords

• Approximation algorithms
• Computer science
• Educational institutions
• NP-hard problem
• Algorithm design and analysis
• DNA
• Data compression
• Polynomials
• Upper bound
• Estimation Algorithm
• Directed Graph
• Algorithm For Problem
• Traveling Salesman Problem
• Total Weight
• Generation Algorithm
• Edge Weights
• Pathfinding
• Problem Of Finding
• Triangle Inequality
• Red Edge
• Previous Algorithms
• Vertex Degree
• Original Graph
• Color Categories
• Undirected Edges
• Incident Edges
• Subset Of Edges
• Hamiltonian Path