Pickel, P. F. An update on the ellipsoid algorithm. (English) Zbl 0568.90062 Discrete geometry and convexity, Proc. Conf., New York 1982, Ann. N.Y. Acad. Sci. 440, 364-380 (1985). [For the entire collection see Zbl 0564.00011.] This paper is a survey of the ellipsoid algorithm and its applications. It includes an analysis of a computational comparison of this algorithm with a generalized reduced gradient code, two quadratic subproblem codes and an augmented Lagrangian code, reported by J. G. Ecker and M. Kupferschmid [Math. Program. 27, 83-106 (1983; Zbl 0526.90074)], and some applications to the derivation of computational complexity results for some problems on perfect graphs due to M. Grötschel, L. Lovász and A. Schrijver [Perfect graphs, Ann. Discrete Math. 21, 325-356 (1984; Zbl 0554.05041)]. Reviewer: J.-E.Martinez-Legaz Cited in 2 Documents MSC: 90C05 Linear programming 68Q25 Analysis of algorithms and problem complexity 05C35 Extremal problems in graph theory 90C25 Convex programming 65K05 Numerical mathematical programming methods 90C30 Nonlinear programming Keywords:Karmarkar’s algorithm; survey; ellipsoid algorithm; computational comparison; generalized reduced gradient; augmented Lagrangian code; computational complexity; perfect graphs Citations:Zbl 0564.00011; Zbl 0526.90074; Zbl 0554.05041 PDFBibTeX XML