Complexity of the gravitational method for linear programming (Q5942223)

The gravitational method to solve a linear program starts by dropping a particle from an interior point of the polyhedron and letting it move under the influence of a gravitational field parallel to the objective function direction. After hitting the boundary of the polyhedron, the particle moves on the surface along the steepest-descent feasible direction, eventually arriving at an optimal solution. It is shown that this simplex-like algorithm needs exponentially many iterations in the worst case. A class of linear programs with \(n\) variables and \(2n\) constraints is constructed in which the above algorithm behaves like the simplex algorithm after the boundary is reached and \(2^n-1\) vertices will be visited; the input bit complexity is \(O(n\log n)\).