A note on bounded weighted graphic metric TSP

Ildikó Czeller, Gyula Pap


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2014},
NUMBER = {TR-2014-03}

Last modification: 13.3.2018. Please email your comments to Tamás Király!