English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the lift-and-project procedures of Lov{\'a}sz-Schrijver andSherali-Adams applied to the standard linear programming relaxation of thetraveling salesperson problem with triangle inequality. For the asymmetric TSPtour problem, Charikar, Goemans, and Karloff (FOCS 2004) proved that theintegrality gap of the standard relaxation is at least 2. We prove that afterone round of the Lov{\'a}sz-Schrijver or Sherali-Adams procedures, theintegrality gap of the asymmetric TSP tour problem is at least 3/2, with asmall caveat on which version of the standard relaxation is used. For thesymmetric TSP tour problem, the integrality gap of the standard relaxation isknown to be at least 4/3, and Cheung (SIOPT 2005) proved that it remains atleast 4/3 after $o(n)$ rounds of the Lov{\'a}sz-Schrijver procedure, where $n$is the number of nodes. For the symmetric TSP path problem, the integrality gapof the standard relaxation is known to be at least 3/2, and we prove that itremains at least 3/2 after $o(n)$ rounds of the Lov{\'a}sz-Schrijver procedure,by a simple reduction to Cheung's result.

Lift-and-Project Integrality Gaps for the Traveling Salesperson Problem