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
SN - 0025-5610
VL - 159
SP - 1
EP - 29
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -