×

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)].

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