Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430573 | Journal of Discrete Algorithms | 2013 | 9 Pages |
Abstract
In this paper, we consider the ordered TSP, a variant of the traveling salesman problem with precedence constraints, where the precedence constraints are such that a given subset of vertices has to be visited in some prescribed linear order. We give improved algorithms for the ordered TSP: For the metric case, we present a polynomial-time algorithm that guarantees an approximation ratio of 2.5−2/k2.5−2/k, where k is the number of ordered vertices. For near-metric input instances satisfying a β -relaxed triangle inequality, we improve the ratio to kβlog2(⌊3k/2⌋+1)kβlog2(⌊3k/2⌋+1).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hans-Joachim Böckenhauer, Tobias Mömke, Monika Steinová,