Feature Article—The Ellipsoid Method: A Survey

TLDR

Khachiyan’s 1979 note proved the ellipsoid method for linear programming is polynomial‑time, sparking rapid excitement and a surge of papers, yet many aspects—its precise nature, practical relevance, implementation, broader applicability, and links to earlier work—remain poorly understood. The authors aim to clarify these issues through a comprehensive survey covering the ellipsoid method’s history, recent advances, and current research. The survey highlights key developments and resolves outstanding questions about the ellipsoid method’s theoretical properties, practical impact, and extensions beyond linear programming.

Abstract

In February 1979 a note by L. G. Khachiyan indicated how an ellipsoid method for linear programming can be implemented in polynomial time. This result has caused great excitement and stimulated a flood of technical papers. Ordinarily there would be no need for a survey of work so recent, but the current circumstances are obviously exceptional. Word of Khachiyan's result has spread extraordinarily fast, much faster than comprehension of its significance. A variety of issues have, in general, not been well understood, including the exact character of the ellipsoid method and of Khachiyans result on polynomiality, its practical significance in linear programming, its implementation, its potential applicability to problems outside of the domain of linear programming, and its relationship to earlier work. Our aim is to help clarify these important issues in the context of a survey of the ellipsoid method, its historical antecedents, recent developments, and current research.