For metric TSP, Christofides' heuristic is still the best known approximation algorithm with its 3/2 guarantee. The set of graphic metrics and the set of (1,2)-metrics are some of the few classes known to admit a better-than-3/2 approximation algorithm. In this paper we investigate TSP for so-called $\beta$-bounded metrics and determine that, for any $\beta \ge 1$, the randomized approach of Oveis Gharan, Saberi and Singh [5] achieves a better-than-3/2 guarantee for $\beta$-bounded metrics. A metric space is called a $\beta$-bounded weighted graphic metric ($\beta$-bounded metric, for short) if it is realized by shortest path distances in a graph with edge-lengths between $1$ and $\beta$. This result broadens the class of metric spaces with a better-than-3/2 approximation guarantee.
Bibtex entry:
@techreport{egres-14-03,
AUTHOR | = | {Czeller, Ildik{\'o} and Pap, Gyula}, |
TITLE | = | {A note on bounded weighted graphic metric TSP}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2014}, |
NUMBER | = | {TR-2014-03} |