Parameterized Traveling Salesman Problem : Beating the Average. / Gutin, Gregory; Patel, Viresh.

In: SIAM Journal on Discrete Mathematics, Vol. 30, No. 1, 04.02.2016, p. 220-238.

Research output: Contribution to journalArticle

E-pub ahead of print

Documents

Links

Abstract

In the Travelling Salesman Problem (TSP), we are given a complete graph $K_n$ together with an integer weighting $w$ on the edges of $K_n$, and we are asked to find a Hamilton cycle of $K_n$ of minimum weight. Let $h(w)$ denote the average weight of a Hamilton cycle of $K_n$ for the weighting $w$. Vizing (1973) asked whether there is a polynomial-time algorithm which always finds a Hamilton cycle of weight at most $h(w)$. He answered this question in the affirmative and subsequently Rublineckii (1973) and others described several other TSP heuristics satisfying this property. In this paper, we prove a considerable generalisation of Vizing's result: for each fixed $k$, we give an algorithm that decides whether, for any input edge weighting $w$ of $K_n$, there is a Hamilton cycle of $K_n$ of weight at most $h(w)-k$ (and constructs such a cycle if it exists). For $k$ fixed, the running time of the algorithm is polynomial in $n$, where the degree of the polynomial does not depend on $k$ (i.e.\ the generalised Vizing problem is fixed-parameter tractable with respect to the parameter $k$).
Original languageEnglish
Pages (from-to)220-238
Number of pages19
JournalSIAM Journal on Discrete Mathematics
Volume30
Issue number1
Early online date4 Feb 2016
DOIs
Publication statusE-pub ahead of print - 4 Feb 2016
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 25784637