Editing Linear programming (section)

==== Ellipsoid algorithm, following Khachiyan ====
This is the first [[worst-case complexity|worst-case]] [[polynomial-time]] algorithm ever found for linear programming.  To solve a problem which has ''n'' variables and can be encoded in ''L'' input bits, this algorithm runs in <math> O(n^6 L) </math> time.<ref name = "khachiyan79" /> [[Leonid Khachiyan]] solved this long-standing complexity issue in 1979 with the introduction of the [[ellipsoid method]]. The convergence analysis has (real-number) predecessors, notably the [[iterative method]]s developed by [[Naum Z. Shor]] and the [[approximation algorithm]]s by Arkadi Nemirovski and D. Yudin.