An Oblivious Ellipsoid Algorithm for Solving a System of (In)Feasible Linear Inequalities

References

• [1] Bland R, Goldfarb D, Todd MJ (1981) The ellipsoid method: A survey. Oper. Res. 29(6):1039–1091.Link, Google Scholar
• [2] Burrell BP, Todd MJ (1985) The ellipsoid method generates dual variables. Math. Oper. Res. 10(4):688–700.Link, Google Scholar
• [3] Cheung D, Cucker F (2001) A new condition number for linear programming. Math. Programming 91:163–174.Crossref, Google Scholar
• [4] Ecker J, Kupferschmid M (1985) A computational comparison of the ellipsoid algorithm with several nonlinear programming algorithms. SIAM J. Control Optim. 23(5):657–674.Crossref, Google Scholar
• [5] Gács P, Lovász L (1981) Khachiyan’s algorithm for linear programming. König H, Korte B, Ritter K, eds. Mathematical Programming at Oberwolfach (Springer, Heidelberg, Germany), 61–68.Crossref, Google Scholar
• [6] Grötschel M, Lovász L, Schrijver A (1994) Geometric Algorithms and Combinatorial Optimization, 2nd ed. (Springer, Berlin)Google Scholar
• [7] Khachiyan LG (1979) A polynomial algorithm in linear programming. Soviet Math. Doklady 20(1):191–194.Google Scholar
• [8] Lamperski J, Freund RM, Todd MJ (2019) An oblivious ellipsoid algorithm for solving a system of (in)feasible linear inequalities. Preprint, submitted October 7, https://doi.org/10.48550/arXiv.1910.03114.Google Scholar
• [9] Renegar J (1994) Some perturbation theory for linear programming. Math. Programming 65(1):73–91.Crossref, Google Scholar
• [10] Renegar J (1995a) Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim. 5(3):506–524.Crossref, Google Scholar
• [11] Renegar J (1995b) Linear programming, complexity theory, and elementary functional analysis. Math. Programming 70(3):279–351.Crossref, Google Scholar
• [12] Shor N (1977) Cut-off method with space extension in convex programming problems. Cybernetics 13:94–96.Crossref, Google Scholar
• [13] Todd MJ (1980) Minimum volume ellipsoids containing part of a given ellipsoid. Math. Oper. Res. 7:253–261.Link, Google Scholar
• [14] Todd MJ (2018) Ellipsoid method redux. Internat. Sympos. Math. Programming, July 1–6, Bordeaux, France.Google Scholar
• [15] Yamnitsky B, Levin L (1982) An old linear programming algorithm runs in polynomial time. Proc. 23rd Annual Sympos. Foundations Comput. Sci. (IEEE, Los Alamitos, CA), 327–328.Google Scholar
• [16] Yudin D, Nemirovsky A (1977) Informational complexity and effective methods of solution for convex extremal problems. Matekon 13:25–45.Google Scholar