Change search
ReferencesLink to record
Permanent link

Direct link
Approximating Graphic TSP by Matchings
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2011 (English)In: Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, IEEE conference proceedings, 2011, 560-569 p.Conference paper (Refereed)
Abstract [en]

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order 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), the approach yields a 1.461-approximation algorithm with respect to the Held-Karp lower bound. For graph-TSP restricted to a class of graphs that contains degree three bounded and claw-free graphs, we show that the integrality gap of the Held-Karp relaxation matches the conjectured ratio 4/3. The framework allows for generalizations in a natural way and also leads to a 1.586-approximation algorithm for the traveling salesman path problem on graphic metrics where the start and end vertices are prespecified.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2011. 560-569 p.
, Annual IEEE Symposium on Foundations of Computer Science, ISSN 0272-5428
Keyword [en]
TSP, approximation, matchings
National Category
Computer Science
URN: urn:nbn:se:kth:diva-59148DOI: 10.1109/FOCS.2011.56ISI: 000298962700060ScopusID: 2-s2.0-84862632630ISBN: 978-1-4577-1843-4OAI: diva2:475131
2011 52nd Annual IEEE Symposium on Foundations of Computer Science, 22-25 Oct. 2011, Palm Springs, CA, USA
ERC Advanced investigator grant 226203ERC grant 228021-ECCSciEng
QC 20120113Available from: 2012-01-10 Created: 2012-01-10 Last updated: 2012-04-02Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Mömke, Tobias
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 35 hits
ReferencesLink to record
Permanent link

Direct link