A recent paper by 3rd year PhD student Thomas Dueholm Hansen from the Department of Computer Science, co-authored by Oliver Friedmann from Ludwig-Maximillans-Universität München and Uri Zwick from Tel Aviv University solves a decades-old open problem in linear programming. They show that even in its randomized incarnations, with high probability, the simplex algorithm for solving linear programs takes near-exponential time to terminate on certain ingenuously constructed inputs. Classical results show that all studied deterministic incarnations of the simplex algorithm had this unfortunate property, but prior to the result of Hansen and his collaborators, it was hoped that this behavior could be avoided using randomization.

2010.11.08 | Ann Eg Mølhave

Linear programs form a class of mathematical models of fundamental theoretical importance in mathematical optimization, and are of huge practical importance in industrial operations research. The simplex algorithm created  by American mathematician George Dantzig in 1947 is the most important algorithm for solving such models in practice, and is known to all computer science and operations research undergraduates.

Peter Bro Miltersen, professor at the computer science department and supervisor for Thomas Dueholm Hansen says: "For ten years, I have been saying in my class on linear programming that this was one of the great unsolved open problems in linear programming. It is very satisfactory and also a bit amazing that it is solved by one of my own students."

Thomas' research is carried out within the Center for Algorithmic Game Theory, funded by the Carlsberg Foundation.

The paper is available at www.cs.au.dk/~tdh/papers/random_edge.pdf