License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.8
URN: urn:nbn:de:0030-drops-172932
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17293/
Friggstad, Zachary ;
Mousavi, Ramin
Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP
Abstract
We initiate the study of the Bounded-Degree Subset Traveling Salesman problem (BDSTSP) in which we are given a graph G = (V,E) with edge cost c_e ≥ 0 on each edge e, degree bounds b_v ≥ 0 on each vertex v ∈ V and a subset of terminals X ⊆ V. The goal is to find a minimum-cost closed walk that spans all terminals and visits each vertex v ∈ V at most b_v/2 times. In this paper, we study bi-criteria approximations that find tours whose cost is within a constant-factor of the optimum tour length while violating the bounds b_v at each vertex by additive quantities.
If X = V, an adaptation of the Christofides-Serdyukov algorithm yields a (3/2, +4)-approximation, that is the tour passes through each vertex at most b_v/2+2 times (the degree of v in the multiset of edges on the tour being at most b_v + 4). This is enabled through known results in bounded-degree Steiner trees and integrality of the bounded-degree Y-join polytope. The general case X ≠ V is more challenging since we cannot pass to the metric completion on X. However, it is at least simple to get a (5/3, +4)-bicriteria approximation by using ideas similar to Hoogeveen’s TSP-Path algorithm.
Our main result is an improved approximation with marginally worse violations of the vertex bounds: a (13/8, +6)-approximation. We obtain this primarily through adapting the bounded-degree Steiner tree approximation to ensure certain "dangerous" nodes always have even degree in the resulting tree which allows us to bound the cost of the resulting degree-bounded Y-join. We also recover a (3/2, +8)-approximation for this general case.
BibTeX - Entry
@InProceedings{friggstad_et_al:LIPIcs.ISAAC.2022.8,
author = {Friggstad, Zachary and Mousavi, Ramin},
title = {{Bi-Criteria Approximation Algorithms for Bounded-Degree Subset TSP}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {8:1--8:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17293},
URN = {urn:nbn:de:0030-drops-172932},
doi = {10.4230/LIPIcs.ISAAC.2022.8},
annote = {Keywords: Linear programming, approximation algorithms, combinatorial optimization}
}
|
Keywords: |
|
Linear programming, approximation algorithms, combinatorial optimization |
|
Collection: |
|
33rd International Symposium on Algorithms and Computation (ISAAC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
