Approximation Algorithms for some Routing Problems

Several polynomial time approximation algorithms for some NP-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strategy heuristic with a bound of 9/5 is presented for the Stacker-Crane problem (a modified Traveling Salesman problem). A tour-splitting heuristic is given for k-person variants of the Traveling Salesman problem, the Chinese Postman problem, and the Stacker-Crane problem, for which a minimax solution is sought. This heuristic has a bound of e + 1 - 1/k, where e is the bound for the corresponding 1-person algorithm.

Authors

• Greg N. Frederickson
• Matthew S. Hecht
• Chul E. Kim

Keywords

• Approximation algorithms
• Routing
• Cost function
• Traveling salesman problems
• Cities and towns
• Polynomials
• Cranes
• Computer science
• Educational institutions
• Minimax techniques
• Routing Problem
• Undirected
• Directed Graph
• Out-degree
• Vertex Degree
• Traveling Salesman Problem
• Multiset
• Multigraph
• Sequence Of Vertices
• Distance Function
• Head And Tail