On the complexity of approximating the maximal inscribed ellipsoid for a polytope
From MaRDI portal
Publication:1315411
DOI10.1007/BF01582144zbMath0792.90088OpenAlexW2055356142MaRDI QIDQ1315411
Michael J. Todd, Leonid G. Khachiyan
Publication date: 10 March 1994
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01582144
Related Items
Most likely maximum entropy for population analysis with region-censored data, On the complexity of some basic problems in computational convexity. I. Containment problems, Finding Minimum Volume Circumscribing Ellipsoids Using Generalized Copositive Programming, On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids, A modification of the inscribed ellipsoid method, Clustering via minimum volume ellipsoids, On the minimum volume simplex enclosure problem for estimating a linear mixing model, Interior-point methods: An old and new approach to nonlinear programming, SHARPENING GEOMETRIC INEQUALITIES USING COMPUTABLE SYMMETRY MEASURES, Algorithms to construct a minimum-volume invariant ellipsoid for a stable dynamic system, A cutting plane algorithm for convex programming that uses analytic centers, How to solve a design centering problem, Relatively Smooth Convex Optimization by First-Order Methods, and Applications, Rank-two update algorithms for the minimum volume enclosing ellipsoid problem, Recursive algorithms for inner ellipsoidal approximation of convex polytopes., A delimitation of the support of optimal designs for Kiefer's \(\phi _p\)-class of criteria, Approximating fixed points of weakly contracting mappings, A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem, Scientific contributions of Leo Khachiyan (a short overview), Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices, A portfolio selection model using fuzzy returns, Minimal ellipsoid circumscribing a polytope defined by a system of linear inequalities, An interior-point smoothing technique for Lagrangian relaxation in large-scale convex programming†, Symmetry of convex sets and its applications to the extremal ellipsoids of convex bodies, Inscribed ball and enclosing box methods for the convex maximization problem, Conditional minimum volume ellipsoid with application to multiclass discrimination, Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids, Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method, Methods of centers for variational inequalities and linear programming, Complexity analysis of logarithmic barrier decomposition methods for semi-infinite linear programming, Playing Billiards in Version Space, Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization, On self-concordant convex–concave functions, Minimum-volume enclosing ellipsoids and core sets
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Über das Löwnersche Ellipsoid und sein Analogon unter den einem Eikörper einbeschriebenen Ellipsoiden
- A polynomial-time algorithm, based on Newton's method, for linear programming
- On the complexity of four polyhedral set containment problems
- A Potential Reduction Algorithm Allowing Column Generation
- Optimal design: Some geometrical aspects of D-optimality
- An Algorithm for Separating Patterns by Ellipsoids
