|
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:
| 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} |