TR-2014-03

A note on bounded weighted graphic metric TSP

Ildikó Czeller, Gyula Pap



Abstract

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


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