TY - JOUR

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

AU - Cheriyan, Joseph

AU - Gao, Zhihan

AU - Georgiou, Konstantinos

AU - Singla, Sahil

N1 - Publisher Copyright:
© 2015, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

PY - 2016/9/1

Y1 - 2016/9/1

N2 - 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).

AB - 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).

KW - Asymmetric TSP

KW - Integrality ratios

KW - Sherali–Adams hierarchy

UR - http://www.scopus.com/inward/record.url?scp=84942040749&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84942040749&partnerID=8YFLogxK

U2 - 10.1007/s10107-015-0947-5

DO - 10.1007/s10107-015-0947-5

M3 - Article

AN - SCOPUS:84942040749

VL - 159

SP - 1

EP - 29

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -