×

Approximation algorithms for the TSP with sharpened triangle inequality. (English) Zbl 1338.68289

Summary: The traveling salesman problem (TSP) is one of the hardest optimization problems in NPO because it does not admit any polynomial-time approximation algorithm (unless \(\operatorname{P}=\operatorname{NP}\)). On the other hand we have a polynomial-time approximation scheme (PTAS) for the Euclidean TSP and the 3/2-approximation algorithm of Christofides for TSP instances satisfying the triangle inequality.{ }In this paper, we consider \(\Delta_\beta\)-TSP, for \(1/2 < \beta < 1\), as a subproblem of the TSP whose input instances satisfy the \(\beta\)-sharpened triangle inequality \(\operatorname{cost}(\{u, v\})\leqslant\beta(\operatorname{cost}(\{u, x\}) + \operatorname{cost}(\{x, v\}))\) for all vertices \(u\), \(v\), \(x\). This problem is APX-complete for every \(\beta > 1/2\). The main contribution of this paper is the presentation of three different methods for the design of polynomial-time approximation algorithms for \(\Delta_\beta\)-TSP with \(1/2 < \beta < 1\), where the approximation ratio lies between 1 and 3/2, depending on \(\beta\).

MSC:

68W25 Approximation algorithms
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C27 Combinatorial optimization
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Arora, S., Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, J. ACM, Vol. 45, 5, 753-782 (1998) · Zbl 1064.90566
[2] Arora, S., Nearly linear time approximation schemes for Euclidean TSP and other geometric problems, (Proc. 38th Annual IEEE Symp. on Foundations of Computer Science (1997)), 554-563
[3] Andreae, T.; Bandelt, H.-J., Performance guarantees for approximation algorithms depending on parametrized triangle inequalities, SIAM J. Discrete Math., Vol. 8, 1-16 (1995) · Zbl 0832.90089
[4] Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M., Complexity and Approximation, Combinatorial Optimization Problems and Their Approximability Properties (1999), Springer: Springer Berlin · Zbl 0937.68002
[5] Bender, M. A.; Chekuri, C., Performance guarantees for the TSP with a parameterized triangle inequality, (Proc. WADS’99. Proc. WADS’99, Lecture Notes in Computer Science, Vol. 1663 (1999), Springer: Springer Berlin), 80-85 · Zbl 1063.68700
[6] Böckenhauer, H.-J.; Hromkovič, J.; Klasing, R.; Seibert, S.; Unger, W., Towards the notion of stability of approximation algorithms and the traveling salesman problem (Extended Abstract), (Proc. CIAC 2000. Proc. CIAC 2000, Lecture Notes in Computer Science (2000), Springer: Springer Berlin), Full version in: Electronic Colloquium on Computational Complexity, Report No. 31 (1999)
[7] Böckenhauer, H.-J.; Hromkovič, J.; Klasing, R.; Seibert, S.; Unger, W., An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality (Extended Abstract), (Proc. STACS-2000. Proc. STACS-2000, Lecture Notes in Computer Science (2000), Springer: Springer Berlin) · Zbl 1028.90044
[8] Christofides, N., Worst-case analysis of a new heuristic for the traveling salesman problem, Technical Report 388 (1976), Graduate School of Industrial Administration, Carnegie-Mellon University: Graduate School of Industrial Administration, Carnegie-Mellon University Pittsburgh, PA
[9] Engebretsen, L., An explicit lower bound for TSP with distances one and two (Extended Abstract), (Proc. STACS’99. Proc. STACS’99, Lecture Notes in Computer Science, Vol. 1563 (1999), Springer: Springer Berlin), 373-382, Full version in: Electronic Colloquium on Computational Complexity, Revision 1 of Report No. 46 (1999)
[10] Edmonds, J.; Johnson, E. L., Matching: A well-solved class of integer linear programs, (Proc. Calgary International Conference on Combinatorial Structures and Their Applications (1970), Gordon and Breach), 89-92 · Zbl 0258.90032
[11] Gabov, H. N.; Tarjan, R. E., Faster scaling algorithms for general graph-matching problems, J. ACM, Vol. 38, 4, 815-853 (1991) · Zbl 0799.68145
[12] (Hochbaum, D. S., Approximation Algorithms for NP-hard Problems (1996), PWS Publishing Company) · Zbl 1368.68010
[13] (Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G.; Shmoys, D. B., The Traveling Salesman Problem (1985), Wiley: Wiley New York) · Zbl 0563.90075
[14] Mitchell, I. S.B., Guillotine subdivisions approximate polygonal subdivisions: Part II—A simple polynomial-time approximation scheme for geometric \(k\)-MST, TSP and related problems, Technical Report (1996), Dept. of Applied Mathematics and Statistics, Stony Brook, NY
[15] (Mayr, E. W.; Prömel, H. J.; Steger, A., Lectures on Proof Verification and Approximation Algorithms. Lectures on Proof Verification and Approximation Algorithms, Lecture Notes in Computer Science, Vol. 1967 (1998), Springer: Springer Berlin) · Zbl 1043.68579
[16] Papadimitriou, Ch.; Yannakakis, M., The traveling salesman problem with distances one and two, Math. Oper. Res., Vol. 18, 1-11 (1993) · Zbl 0778.90057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.