File(s) under permanent embargo
Approximation hardness of Travelling Salesman via weighted amplifiers
conference contribution
posted on 2023-06-09, 19:06 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková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 123/122 ([9]) to 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.
History
Publication status
- Published
File Version
- Published version
Journal
Computing and CombinatoricsPublisher
SpringerExternal DOI
Volume
11653Page range
115-127Event name
International Computing and Combinatorics Conference (COCOON 2019)Event location
ChinaEvent type
conferenceEvent date
2019Place of publication
Cham, SwitzerlandISBN
978-3-030-26175-7Series
Lecture Notes in Computer ScienceDepartment affiliated with
- Mathematics Publications
Full text available
- No
Peer reviewed?
- Yes
Editors
Z Duan, D Z Du, C TianLegacy Posted Date
2019-09-23First Open Access (FOA) Date
2019-09-23First Compliant Deposit (FCD) Date
2019-09-20Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC