Weighted amplifiers and inapproximability results for Travelling Salesman problem
- PDF / 489,510 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 104 Downloads / 228 Views
Weighted amplifiers and inapproximability results for Travelling Salesman problem Miroslav Chlebík1
· Janka Chlebíková2
Accepted: 5 October 2020 © The Author(s) 2020
Abstract The expander graph constructions and their variants are the main tool used in gap preserving reductions to prove approximation lower bounds of combinatorial optimisation problems. In this paper we introduce the weighted amplifiers and weighted low occurrence of Constraint Satisfaction problems as intermediate steps in the NP-hard gap reductions. Allowing the weights in intermediate problems is rather natural for the edge-weighted problems as Travelling Salesman or Steiner Tree. We demonstrate the technique for Travelling Salesman and use the parametrised weighted amplifiers in the gap reductions to allow more flexibility in fine-tuning their expanding parameters. The purpose of this paper is to point out effectiveness of these ideas, rather than to optimise the expander’s parameters. Nevertheless, we show that already slight improvement of known expander values modestly improve the current 123 (Karpinski et al. in J Comput best approximation hardness value for TSP from 122 117 Syst Sci 81(8):1665–1677, 2015) to 116 . This provides a new motivation for study of expanding properties of random graphs in order to improve approximation lower bounds of TSP and other edge-weighted optimisation problems. Keywords Travelling Salesman problem · Approximation hardness · Probabilistic graph constructions
A preliminary version of this paper was accepted at the 25th International Computing and Combinatorics conference (COCOON), July 29–31, 2019, Xian, China (Chlebík and Chlebíková 2019).
B B
Miroslav Chlebík [email protected] Janka Chlebíková [email protected]
1
Department of Mathematics, University of Sussex, Brighton, UK
2
School of Computing, University of Portsmouth, Portsmouth, UK
123
Journal of Combinatorial Optimization
1 Introduction The Travelling Salesman problem (TSP) is undoubtedly one of the most famous combinatorial optimisation problems. In its standard version, we are given an edgeweighted (undirected) graph and the goal is to find a closed tour with a minimum cost that visits each vertex at least once. This is equivalent to the Graphic Travelling Salesman problem (where the cost between any two vertices corresponds to their shortest path in a graph) and where exactly one visit per vertex is allowed. The Graphic TSP plays an important role in understanding complexity of more general the Metric TSP problem where cost function c : V × V → R+ is defined by a metric. The approximability of the Metric TSP is a long-standing open problem, Christofides’s approximation algorithm with ratio 1.5 (Christofides 1976) hasn’t been improved for more than four decades. It is generally believed that the approximation ratio can be close to 4/3 due to known integrality gap for the Held-Karp LP relaxation (Held and Karp 1970). In the last decade, some significant progress has been done in the Graphic TSP. Gharan et al. (2011) made f
Data Loading...
