The traveling salesman problem: new polynomial approximation algorithms and domination analysis
- 1 January 2001
- journal article
- research article
- Published by Taylor & Francis in Journal of Information and Optimization Sciences
- Vol. 22 (1) , 191-206
- https://doi.org/10.1080/02522667.2001.10699482
Abstract
For the traveling salesman problem (TSP) on n nodes, we show that a tour which is better than ω((n/2)!) alternative tours can be identified in O(n 3) time. Also we provide another algorithm of complexity O n 3) which is guaranteed to produce a solution which is better than ω(n/(k+1))!(k!) n/(k+1) alternative tours, whenever k is fixed. Further we show that by using an O(n 4) algorithm, a TSP tour which dominates ω((n/2)!n) alternative tours can be identified. We also suggest an O(n 5) algorithm with improved domination number.Keywords
This publication has 5 references indexed in Scilit:
- The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithmsJournal of the Operational Research Society, 1997
- Improved complexity bound for the maximum cardinality bottleneck bipartite matching problemDiscrete Applied Mathematics, 1994
- A new heuristic for the traveling salesman problemRairo-Operations Research, 1990
- Halin graphs and the travelling salesman problemMathematical Programming, 1983
- The Bottleneck Traveling Salesman ProblemJournal of the ACM, 1978