TY - GEN

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

AU - Cheriyan, Joseph

AU - Gao, Zhihan

AU - Georgiou, Konstantinos

AU - Singla, Sahil

PY - 2013

Y1 - 2013

N2 - We study the ATSP (Asymmetric Traveling Salesman Problem), 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 LP (linear programming) 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 ≈ 4/3, 6/5, 8/7,.... 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 ATSP (Asymmetric Traveling Salesman Problem), 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 LP (linear programming) 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 ≈ 4/3, 6/5, 8/7,.... 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).

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

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

U2 - 10.1007/978-3-642-39206-1_29

DO - 10.1007/978-3-642-39206-1_29

M3 - Conference contribution

AN - SCOPUS:84880260780

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 340

EP - 351

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -