Zhou, Jianqi ;
Li, Peihua ;
Guo, Jiong
Parameterized Approximation Algorithms for TSP
Abstract
We study the Traveling Salesman problem (TSP), where given a complete undirected graph G = (V,E) with n vertices and an edge cost function c:E↦R_{⩾0}, the goal is to find a minimumcost cycle visiting every vertex exactly once. It is wellknown that unless P = NP, TSP cannot be approximated in polynomial time within a factor of ρ(n) for any computable function ρ, while the metric case of TSP, that the edge cost function satisfies the △inequality, admits a polynomialtime 1.5approximation. We investigate TSP on general graphs from the perspective of parameterized approximability. A parameterized ρapproximation algorithm returns a ρapproximation solution in f(k)⋅I^O(1) time, where f is a computable function and k is a parameter of the input I. We introduce two parameters, which measure the distance of a given TSPinstance from the metric case, and achieve the following two results:
 A 3approximation algorithm for TSP in O((3k₁)! 8^k₁⋅ n²+n³) time, where k₁ is the number of triangles in which the edge costs violate the △inequality.
 A 3approximation algorithm for TSP in O(n^O(k₂)) time and a (6k₂+9)approximation algorithm for TSP in O(k₂^O(k₂)⋅n³) time, where k₂ is the minimum number of vertices, whose removal results in a metric graph.
To our best knowledge, the above algorithms are the first nontrivial parameterized approximation algorithms for TSP on general graphs.
BibTeX  Entry
@InProceedings{zhou_et_al:LIPIcs.ISAAC.2022.50,
author = {Zhou, Jianqi and Li, Peihua and Guo, Jiong},
title = {{Parameterized Approximation Algorithms for TSP}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {50:150:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772587},
ISSN = {18688969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17335},
URN = {urn:nbn:de:0030drops173358},
doi = {10.4230/LIPIcs.ISAAC.2022.50},
annote = {Keywords: FPTapproximation algorithms, the Traveling Salesman problem, the triangle inequality, fixedparameter tractability, metric graphs}
}
14.12.2022
Keywords: 

FPTapproximation algorithms, the Traveling Salesman problem, the triangle inequality, fixedparameter tractability, metric graphs 
Seminar: 

33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Issue date: 

2022 
Date of publication: 

14.12.2022 