Complexity of the gravitational method for linear programming

In the gravitational method for linear programming, a particle is dropped from an interior point of the polyhedron and is allowed to move under the influence of a gravitational field parallel to the objective function direction. Once the particle falls onto the boundary of the polyhedron, its subsequent motion is constrained to be on the surface of the polyhedron with the particle moving along the steepest-descent feasible direction at any instant. Since an optimal vertex minimizes the gravitational potential, computing the trajectory of the particle yields an optimal solution to the linear program. Since the particle is not constrained to move along the edges of the polyhedron as the simplex method does, the gravitational method seemed to have the promise of being theoretically more efficient than the simplex method. In this paper, we first show that, if the particle has zero diameter, then the worst-case time complexity of the gravitational method is exponential in the size of the input linear program. As a simple corollary of the preceding result, it follows that, even when the particle has a fixed nonzero diameter, the gravitational method has exponential time complexity. The complexity of the version of the gravitational method in which the particle diameter decreases as the algorithm progresses remains an open question.