Remote Blogging: Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?

Here are some links and posts related to some of the talks in IPAM’s workshop “Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?” I will be happy to add links to pdf’s of the presentations and to relevant papers. Descriptions and remarks on individual lectures are very welcome. In particular you are most welcome to post here the posters/abstract/papers from the poster session. (Because of some technical matters I will have to miss the workshop. I hope to be able somehow to follow it from far away.)

Following is a description of some of the lectures and some useful links for a few lectures:

A counterexample to Hirsch’s conjecture: Posts related to Paco Santo’s lecture (Tuesday morning) describing a counter example to Hirsch’s conjecture are here and here The second post contains a link to Paco’s paper. Fred Holt’s second lecture will describe some new consequence to Paco’s construction. 

Acyclic USO: Acyclic unique sink orientations (Acyclic USO) of cubes and more general polytopes are mentioned in this post about abstract linear objective functions as well as this one about telling simple polytopes from their graphs. Acyclic USO are mentioned discussed in David Avis’s Wednesday morning talk and a few others.

Stochastic games: Stochastic games relevant to Yinyu Ye’s and Oliver Friedmann’s Thursday morning talks are discussed in this post. Some background (and links to the papers) for the new subexponential lower bounds for randomized pivot rules that will be described in Friedmann’s lecture can be found in this post. 

Polynomial Hirsch conjecture: Ed Kim’s (Thursday afternoon) and Nicolai Hähnle’s  (Friday’s morning) talks are related to polymath3. David Bremner will discuss (Tuesday afternoon) the combinatorics and geometry of path complexes. Jonathan Kelner will propose (Friday morning) a geometric/probabilistic method based on smoothed analysis to attack th epolynomial Hirsch conjecture.

Bad behavior of the simplex algorithms. Examples for the bad behavior of simplex type algorithms (mainly in three dimensions) will be described in Günter Ziegler’s talk (Tuesday afternoon). Here is the link to Günter’s slides which are rather detailed. Bernd Gärtner (Wednesday morning) will demonstrate how Goldfarb’s cubes can be used to refute a conjecture regarding an algorithm for machine learning. 

Interior point methods: Since the mid 80s interior point methods for linear programming are as important theoretically and practically as simplex type algorithms. (I will add a link for a good wide-audience description of interior point methods HERE.) Jim Renegar’s Thursday afternoon lecture will describe some new advances on  Central Swaths (a generalization of the central path a central notion for interior point methods. ) Santosh Vampala closing lecture will propose a hybrid vertex-following interior-type algorithm.

Continuous analogs: There are several interesting continuous analogs for combinatorial notions and questions related to the simplex algorithms. Yuriy Zinchenko will discuss (Wednesday afternoon) continuous analogs of the Hirsch conjecture

Walking on the arragements: Consider the entire arrangement of hyperplanes described by the inequalities of an LP problem. The simplex algorithm can be described as a walk on vertices of this arrangements. Those are very special vertices – the vertices of the feasible polyhedron. The dual simplex algorithm can also be described as a walk on vertices of the arrangement. This time the relevant vertices (I think) are dual-feasible, namely those are vertices of the arrangement which optimize the objective function w.r.t. a subset of the inequalities.  What about LP algorithms based on more general type of walks?  Kumei Fukuda Thursday’s afternoon talk will discuss this issue.  

A new polynomial LP algorithm:  Sergei Chubanov (Thursday afternoon) will propose a strongly polynomial relaxation-type algorithm which either finds a solution of a linear system or decides that the system has no 0,1-solutions. If the system is feasible and the bounds on variables are tight, the algorithm always finds a solution. Sergei will continue to show that the algorithm can be used as the basis for the construction of a polynomial algorithm for linear programming. Here is a link to the paper. Tamás Terlaky (Wednesday afternoon) will review several algorithms for linear programming including elimination and pivot algorithms, interior point methods and the perceptron algorithm.

Complexity of Delaunay Triangulation:  Nina Amenta’s Friday talk will describe what we recently learned about the the complexity of Delaunay triangulations as function of the distribution of their vertices, and will raise the question “how much of this can be applied to polytopes in general?”

Among the additional presentations: Christophe Weibel presented an improvement to Paco Santos’ counterexample. Jésus de Loera presented a paper with Bernd Sturmfels, and Cynthia Vinzant on the centeral curve in linear programming.