Approximation Hardness of Travelling Salesman via Weighted Amplifiers
| Autor: | Miroslav Chlebík, Janka Chlebíková |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
Random graph 021103 operations research Current (mathematics) Computer science 0211 other engineering and technologies Order (ring theory) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Steiner tree problem Travelling salesman problem symbols.namesake 010201 computation theory & mathematics symbols Expander graph Point (geometry) Constraint satisfaction problem |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030261757 COCOON |
| Popis: | 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 best approximation hardness value for TSP from \(\frac{123}{122}\) ([9]) to \(\frac{117}{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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|