Skip to main content
SpringerLink
Log in

Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes

  • Discussion
  • Published:
TOP Aims and scope Submit manuscript

Abstract

This short discussion paper comments on Francisco Santos’ excellent review paper Recent Progress on the Combinatorial Diameter of Polytopes and Simplicial Complexes. We provide some notes on a few closely related topics that were not covered in the survey paper, such as: some relaxed version of the Hirsch conjecture; computability depending on problem data; and continuous versions of the Hirsch conjecture.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. The traditional term Linear Programming is used in Santos (2013), while we prefer to use the term Linear Optimization that is more reflective to the mathematical nature of the problem, without giving the misleading association to computer programming.

References

  • Dantzig GB (1963) Linear programming and extensions. Princeton University Press, Princeton

    Google Scholar 

  • Deza A, Terlaky T, Zinchenko Y (2008a) Polytopes and arrangements: diameter and curvature. Oper Res Lett 36(2):215–222 (Joint work with)

    Article  Google Scholar 

  • Deza A, Terlaky T, Xie F, Zinchenko Y (2008b) Diameter and curvature: intriguing analogies. Electron Notes Discrete Math 31:221–225

    Article  Google Scholar 

  • Deza A, Terlaky T, Zinchenko Y (2009) The continuous d-step conjecture for polytopes. Discrete Comput Geom 41:318–327

    Article  Google Scholar 

  • Fukuda K, Terlaky T (1997) Criss-cross methods: a fresh view on pivot algorithms. Math Program, Ser B 79(1–3):369–395

    Google Scholar 

  • Fukuda K, Terlaky T (2000) On the existence of short admissible pivot sequences for feasibility and liner optimization problems. Pure Math Appl 10(4):431–488

    Google Scholar 

  • Fukuda K, Lüthi H-J, Namiki M (1997) The existence of a short sequence of admissible pivots to an optimal basis in LP and LCP. Int Trans Oper Res 4:273–284

    Article  Google Scholar 

  • Khachiyan LG (1979) A polynomial algorithm in linear programming. Dokl Akad Nauk SSSR 244:1093–1096. Translated into English in Sov Math Dokl 20:191–194

    Google Scholar 

  • Klafszky E, Terlaky T (1992) On the ellipsoid method. Rad Mat 8:269–280

    Google Scholar 

  • Malajovich G, Dedieu J-P, Shub M (2005) On the curvature of the central path of linear programming theory. Found Comput Math 5:145–171

    Article  Google Scholar 

  • Roos C, Terlaky T, Vial J-P (2006) Interior point methods for linear optimization. Springer, Heidelberg

    Google Scholar 

  • Santos F (2013) In: Recent progress on the combinatorial diameter of polytopes and simplicial complexes. TOP this issue

    Google Scholar 

  • Schrijver A (1986) Theory of linear and integer programming. Wiley, New York

    Google Scholar 

  • Terlaky T (1985) A convergent criss–cross method. Optimization 16(5):683–690

    Article  Google Scholar 

  • Terlaky T (1997) A finite criss–cross method for oriented matroids. J Comb Theory, Ser B 42(3):319–327

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, Lehigh University, 200 West Packer Avenue, Bethlehem, PA, 18015-1582, USA

    Tamás Terlaky

Authors
  1. Tamás Terlaky
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tamás Terlaky.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Terlaky, T. Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes. TOP 21, 461–467 (2013). https://doi.org/10.1007/s11750-013-0293-9

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-013-0293-9

Keywords

Mathematics Subject Classification (2010)

Search

Navigation