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 e, 0 ＜ ε 1, there exists a digraph G on v = v(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,..., θ(v) 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 v(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).
展开▼
