Approximation hardness of Travelling Salesman via weighted amplifiers

Miroslav Chlebik, Janka Chlebikova

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

162 Downloads (Pure)


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
Number of pages12
ISBN (Electronic)978-3-030-26176-4
ISBN (Print)978-3-030-26175-7
Publication statusPublished - Aug 2019
EventCOCOON 2019: The 25th International Computing and Combinatorics Conference - Xian, China
Duration: 29 Jul 201931 Jul 2019

Publication series

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


ConferenceCOCOON 2019
Internet address


  • Travelling Salesman Problem
  • weighted amplifiers
  • inapproximability results


Dive into the research topics of 'Approximation hardness of Travelling Salesman via weighted amplifiers'. Together they form a unique fingerprint.

Cite this