Skip to content

Approximation hardness of Travelling Salesman via weighted amplifiers

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.
Original languageEnglish
Title of host publicationComputing and Combinatorics - 25th International Conference, COCOON 2019, Xian, China, July 29 -31, 2019, Proceedings
EditorsDing-Zhu Du, Zhenhua Duan, Cong Tian
PublisherSpringer
Pages115-127
Number of pages12
ISBN (Electronic)978-3-030-26176-4
ISBN (Print)978-3-030-26175-7
DOIs
Publication statusPublished - Aug 2019
EventCOCOON 2019: The 25th International Computing and Combinatorics Conference - Xian, China
Duration: 29 Jul 201931 Jul 2019
http://ictt.xidian.edu.cn/COCOON2019/html/Program.html

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11653
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceCOCOON 2019
CountryChina
CityXian
Period29/07/1931/07/19
Internet address

Documents

  • Approximation hardness postprint

    Rights statement: The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-030-26176-4_10.

    Accepted author manuscript (Post-print), 355 KB, PDF document

Related information

Relations Get citation (various referencing formats)

ID: 15620924