Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-20T00:02:52.527Z Has data issue: false hasContentIssue false
  • English
  • Français

Improved approximations for ordered TSP on near-metric graphs∗∗∗

Published online by Cambridge University Press:  06 November 2014

Hans-Joachim Böckenhauer  and
Monika Steinová Steinová
Hans-Joachim Böckenhauer
Affiliation:
Department of Computer Science, ETH Zurich, Switzerland.. [email protected],[email protected]
Monika Steinová Steinová
Affiliation:
Department of Computer Science, ETH Zurich, Switzerland.. [email protected],[email protected]
Get access

Abstract

The traveling salesman problem is one of the most important problems in operations research, especially when additional precedence constraints are considered. Here, we consider the well-known variant where a linear order on k special vertices is given that has to be preserved in any feasible Hamiltonian cycle. This problem is called Ordered TSP and we consider it on input instances where the edge-cost function satisfies a β-relaxed triangle inequality, i.e., where the length of a direct edge cannot exceed the cost of any detour via a third vertex by more than a factor of β> 1. We design two new polynomial-time approximation algorithms for this problem. The first algorithm essentially improves over the best previously known algorithm for almost all values of k and β< 1.087889. The second algorithm gives a further improvement for 2n ≥ 11k + 7 and β< √34/3 , where n is the number of vertices in the graph.

Keywords

Approximation algorithmnear-metric ordered TSPrelaxed triangle inequality
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 48 , Issue 5 , December 2014 , pp. 479 - 494
Copyright
© EDP Sciences 2014

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Andreae, T., On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality. Networks 38 (2001) 59–67. Google Scholar
Andreae, T. and Bandelt, H.-J., Performance guarantees for approximation algorithms depending on parametrized triangle inequalities. SIAM J. Discrete Math. 8 (1995) 1–16. Google Scholar
Arora, S., Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45 (1998) 753–782. Google Scholar
Bandelt, H.-J., Crama, Y. and Spieksma, F.C.R., Approximation algorithms for multi-dimensional assignment problems with decomposable costs. Discrete Appl. Math. 49 (1994) 25–50. Google Scholar
Bender, M. and Chekuri, C., Performance guarantees for TSP with a parametrized triangle inequality. Inf. Proc. Lett. 73 (2000) 17–21. Google Scholar
H.-J. Böckenhauer and M. Steinová, Improved approximations for ordered TSP on near-metric graphs. In Proc. of the 39th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2013). Vol. 7741 of Lect. Notes Comput. Sci. Springer (2013) 157–168.
Böckenhauer, H.-J., Hromkovič, J., Klasing, R., Seibert, S. and Unger, W., Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Theoret. Comput. Sci. 285 (2002) 3–24. Google Scholar
H.-J. Böckenhauer, J. Hromkovič, J. Kneis and J. Kupke, On the approximation hardness of some generalizations of TSP (extended abstract), in Proc. of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Vol. 4059 of Lect. Notes Comput. Sci. Springer (2006) 184–195.
H.-J. Böckenhauer, R. Klasing, T. Mömke and M. Steinová, Improved approximations for TSP with simple precedence constraints. In Proc. of the 7th International Conference on Algorithms and Complexity (CIAC 2010). Vol. 6078 of Lect. Notes Comput. Sci. Springer (2010) 61–72.
Böckenhauer, H.-J., Mömke, T. and Steinová, M., Improved approximations for TSP with simple precedence constraints. J. Discrete Algorithms 21 (2013) 32–40. Google Scholar
N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388. Graduate School of Industrial Administration, Carnegie-Mellon University (1976).
R. Diestel, Graph Theory. Springer, 3rd edition (2005).
T.F. Gonzalez, Handbook of Approximation Algorithms and Metaheuristics. Chapman & Hall/CRC Computer and Information Science Series. Chapman & Hall/CRC (2007).
G. Gutin and A.P. Punnen, The Traveling Salesman Problem and Its Variations. Combinatorial Optimization. Springer, New York (2007).
J. Hromkovič, Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer (2003).
D.B. West, Introduction to Graph Theory. Prentice Hall Inc., Upper Saddle River, NJ, 2nd edition (2000).