Adamaszek, Anna ;
Mnich, Matthias ;
Paluch, Katarzyna
New Approximation Algorithms for (1,2)TSP
Abstract
We give faster and simpler approximation algorithms for the (1,2)TSP problem, a wellstudied variant of the traveling salesperson problem where all distances between cities are either 1 or 2.
Our main results are two approximation algorithms for (1,2)TSP, one with approximation factor 8/7 and run time O(n^3) and the other having an approximation guarantee of 7/6 and run time O(n^{2.5}). The 8/7approximation matches the best known approximation factor for (1,2)TSP, due to Berman and Karpinski (SODA 2006), but considerably improves the previous best run time of O(n^9). Thus, ours is the first improvement for the (1,2)TSP problem in more than 10 years. The algorithm is based on combining three copies of a minimumcost cycle cover of the input graph together with a relaxed version of a minimum weight matching, which allows using "halfedges". The resulting multigraph is then edgecolored with four colors so that each color class yields a collection of vertexdisjoint paths. The paths from one color class can then be extended to an 8/7approximate traveling salesperson tour. Our algorithm, and in particular its analysis, is simpler than the previously best 8/7approximation.
The 7/6approximation algorithm is similar and even simpler, and has the advantage of not using Hartvigsen's complicated algorithm for computing a minimumcost trianglefree cycle cover.
BibTeX  Entry
@InProceedings{adamaszek_et_al:LIPIcs:2018:9013,
author = {Anna Adamaszek and Matthias Mnich and Katarzyna Paluch},
title = {{New Approximation Algorithms for (1,2)TSP}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {9:19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9013},
URN = {urn:nbn:de:0030drops90133},
doi = {10.4230/LIPIcs.ICALP.2018.9},
annote = {Keywords: Approximation algorithms, traveling salesperson problem, cycle cover}
}
2018
Keywords: 

Approximation algorithms, traveling salesperson problem, cycle cover 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

2018 