[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content

Advertisement

Springer Nature Link
Log in

On the \({\mathcal {H}}\)-free extension complexity of the TSP

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

It is known that the extension complexity of the TSP polytope for the complete graph \(K_n\) is exponential in n even if the subtour inequalities are excluded. In this article we study the polytopes formed by removing other subsets \({\mathcal {H}}\) of facet-defining inequalities of the TSP polytope. In particular, we consider the case when \({\mathcal {H}}\) is either the set of blossom inequalities or the simple comb inequalities. These inequalities are routinely used in cutting plane algorithms for the TSP. We show that the extension complexity remains exponential even if we exclude these inequalities. In addition we show that the extension complexity of polytope formed by all comb inequalities is exponential. For our proofs, we introduce a subclass of comb inequalities, called (h, t)-uniform inequalities, which may be of independent interest.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Notes

  1. W. Cook (private communication) attributes the same argument to T. Rothvoß.

References

  1. Avis, D., Tiwary, H.R.: On the extension complexity of combinatorial polytopes. In: ICALP, pp. 57–68 (2013)

  2. Avis, D., Tiwary, H.R.: A generalization of extension complexity that captures P. Inf. Process. Lett. 115(6–8), 588–593 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  3. Conforti, M., Cornuéjols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR 8, 1–48 (2010)

  4. Faenza, Y., Fiorini, S., Grappe, R., Tiwary, H.R.: Extended formulations, nonnegative factorizations, and randomized communication protocols. In: ISCO, pp. 129–140 (2012)

  5. Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: STOC, pp. 95–106 (2012)

  6. Fleischer, L., Letchford, A.N., Lodi, A.: Polynomial-time separation of a superclass of simple comb inequalities. Math. Oper. Res. 31(4), 696–713 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  7. Grötschel, M., Padberg, M.: On the symmetric travelling salesman problem II: lifting theorems and facets. Math. Program. 16(1), 281–302 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  8. Padberg, M., Rao, M.R.: Odd minimum cut-sets and \(b\)-matchings. Math. Oper. Res. 7, 67–80 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  9. Pokutta, S., Vyve, M.V.: A note on the extension complexity of the knapsack polytope. Oper. Res. Lett. 41(4), 347–350 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  10. Rothvoß, T.: The matching polytope has exponential extension complexity. In: STOC, pp. 263–272 (2014)

Download references

Acknowledgments

Research of the first author is supported by a Grant-in-Aid for Scientific Research on Innovative Areas—Exploring the Limits of Computation, MEXT, Japan. Research of the second author is partially supported by GA ČR Grant P202-13/201414.

Author information

Authors and Affiliations

  1. Graduate School of Informatics, Kyoto University, Sakyo-ku, Yoshida, Kyoto, 606-8501, Japan

    David Avis

  2. KAM/ITI, Charles University, Malostranské nám. 25, 118 00, Prague 1, Czech Republic

    Hans Raj Tiwary

Authors
  1. David Avis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hans Raj Tiwary
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hans Raj Tiwary.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Avis, D., Tiwary, H.R. On the \({\mathcal {H}}\)-free extension complexity of the TSP. Optim Lett 11, 445–455 (2017). https://doi.org/10.1007/s11590-016-1029-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-016-1029-1

Keywords

Search

Navigation