Obtaining Quality-Proved Near Optimal Results for Traveling Salesman Problem
Preprint
Abstract
The traveling salesman problem (TSP) is one of the most challenging NP-hard problems. It has widely applications in various disciplines such as physics, biology, computer science and so forth. The best known approximation algorithm for Symmetric TSP (STSP) whose cost matrix satisfies the triangle inequality (called $\triangle$STSP) is Christofides algorithm which was proposed in 1976 and is a $\frac{3}{2}$-approximation. Since then no proved improvement is made and improving upon this bound is a fundamental open question in combinatorial optimization. In this paper, for the first time, we propose Truncated Generalized Beta distribution (TGB) for the probability distribution of optimal tour lengths in a TSP. We then introduce an iterative TGB approach to obtain quality-proved near optimal approximation, i.e., (1+$\frac{1}{2}(\frac{\alpha+1}{\alpha+2})^{K-1}$)-approximation where $K$ is the number of iterations in TGB and $\alpha (>>1)$ is the shape parameters of TGB. The result can approach the true optimum as $K$ increases.
Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Improving Christofides' Algorithm for the s-t Path TSPJournal of the ACM, 2015
- General k-opt submoves for the Lin–Kernighan TSP heuristicMathematical Programming Computation, 2009
- On estimating the distribution of optimal traveling salesman tour lengths using heuristicsEuropean Journal of Operational Research, 2008
- Chained Lin-Kernighan for Large Traveling Salesman ProblemsINFORMS Journal on Computing, 2003
- TSPLIB—A Traveling Salesman Problem LibraryINFORMS Journal on Computing, 1991
- An Effective Heuristic Algorithm for the Traveling-Salesman ProblemOperations Research, 1973
- Discrete Optimizing Solution Procedures for Linear and Nonlinear Integer Programming ProblemsManagement Science, 1966