Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2014-15 > On the polynomial Hirsch conjecture and its continuous analogue
How to contact us

 

LSE 10 logo master_6


Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE

  

Enquiries: dom.events@lse.ac.uk 

  

Follow us online

Facebook-Square-38x38Twitter-square-38x38Youtube-square-38x38

 

On the polynomial Hirsch conjecture and its continuous analogue

Wednesday 11 February 2015
Antoine Deza

4pm - 5pm, OLD 1.27, Old Building, Houghton Street 


Abstract

The simplex and primal-dual interior point methods are the most computationally successful algorithms for linear optimization. While simplex methods follow an edge path, interior point methods follow the central path. Within this framework, the curvature of a polytope, defined as the largest possible total curvature of the associated central path, can be regarded as the continuous analogue of its diameter. In this talk, we highlight links between the edge and central paths, and between the diameter and the curvature of a polytope. We recall continuous results of Dedieu, Malajovich, and Shub, and discrete results of Holt and Klee and of Klee and Walkup, as well as related conjectures such as the Hirsch conjecture that was disproved by Santos. We also present analogous results dealing with average and worst-case behaviour of the curvature and diameter of polytopes, including a result of Allamigeon, Benchimol, Gaubert, and Joswig who constructed a counterexample to the continuous analogue of the polynomial Hirsch conjecture. Based on joint work with Tamás Terlaky (Lehigh), Feng Xie (Microsoft), and Yuriy Zinchenko (Calgary).

Share:Facebook|Twitter|LinkedIn|
ADeza