On integrality ratios for asymmetric TSP in the Sherali–Adams hierarchy

Joseph Cheriyan, Zhihan Gao, Konstantinos Georgiou, Sahil Singla

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We study the Asymmetric Traveling Salesman Problem (ATSP), and our focus is on negative results in the framework of the Sherali–Adams (SA) Lift and Project method. Our main result pertains to the standard linear programming (LP) relaxation of ATSP, due to Dantzig, Fulkerson, and Johnson. For any fixed integer t≥ 0 and small ϵ, 0 < ϵ≪ 1 , there exists a digraph G on ν= ν(t, ϵ) = O(t/ ϵ) vertices such that the integrality ratio for level t of the SA system starting with the standard LP on G is ≥1+1-ϵ2t+3≈43,65,87,…. Thus, in terms of the input size, the result holds for any t= 0 , 1 , … , Θ(ν) levels. Our key contribution is to identify a structural property of digraphs that allows us to construct fractional feasible solutions for any level t of the SA system starting from the standard LP. Our hard instances are simple and satisfy the structural property. There is a further relaxation of the standard LP called the balanced LP, and our methods simplify considerably when the starting LP for the SA system is the balanced LP; in particular, the relevant structural property (of digraphs) simplifies such that it is satisfied by the digraphs given by the well-known construction of Charikar, Goemans and Karloff (CGK). Consequently, the CGK digraphs serve as hard instances, and we obtain an integrality ratio of 1+1-ϵt+1 for any level t of the SA system, where 0 < ϵ≪ 1 and the number of vertices is ν(t, ϵ) = O((t/ ϵ) (t/ϵ)). Also, our results for the standard LP extend to the path ATSP (find a min cost Hamiltonian dipath from a given source vertex to a given sink vertex).

Original languageEnglish (US)
Pages (from-to)1-29
Number of pages29
JournalMathematical Programming
Volume159
Issue number1-2
DOIs
StatePublished - Sep 1 2016

All Science Journal Classification (ASJC) codes

  • Software
  • General Mathematics

Keywords

  • Asymmetric TSP
  • Integrality ratios
  • Sherali–Adams hierarchy

Fingerprint

Dive into the research topics of 'On integrality ratios for asymmetric TSP in the Sherali–Adams hierarchy'. Together they form a unique fingerprint.

Cite this