Thumbnail
Access Restriction
Subscribed

Author Mmke, Tobias ♦ Svensson, Ola
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Approximation ♦ TSP ♦ Linear programming
Abstract We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a decreased cost. For the TSP on graphic metrics (graph-TSP), we show that the approach gives a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted either to half-integral solutions to the Held-Karp relaxation or to a class of graphs that contains subcubic and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework also allows for generalizations in a natural way and leads to analogous results for the $\textit{s},$ $\textit{t}-path$ traveling salesman problem on graphic metrics where the start and end vertices are prespecified.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-02-12
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 1
Page Count 28
Starting Page 1
Ending Page 28


Source: ACM Digital Library