Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Removing and Adding Edges for the Traveling Salesman Problem
 
research article

Removing and Adding Edges for the Traveling Salesman Problem

Moemke, Tobias
•
Svensson, Ola  
2016
Journal Of The Acm

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 s, t-path traveling salesman problem on graphic metrics where the start and end vertices are prespecified.

  • Details
  • Metrics
Type
research article
DOI
10.1145/2739008
Web of Science ID

WOS:000373852100002

Author(s)
Moemke, Tobias
Svensson, Ola  
Date Issued

2016

Publisher

Assoc Computing Machinery

Published in
Journal Of The Acm
Volume

63

Issue

1

Start page

2

Subjects

Algorithms

•

Theory

•

Approximation

•

linear programming

•

TSP

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
THL2  
Available on Infoscience
July 19, 2016
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/127462
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés