2014/08/03 by Gregory Gutin, Gutin, Gregory, Viresh Patel +1
Computer Science · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.1408.0531
arxiv created 2014/08/03 · arxiv updated 2014/08/05
In the Travelling Salesman Problem (TSP), we are given a complete graph Kn together with an integer weighting w on the edges of Kn, and we are asked to find a Hamilton cycle of Kn of minimum weight. Let h(w) denote the average weight of a Hamilton cycle of Kn 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 Kn, there is a Hamilton cycle of Kn 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).