On the complexity of approximating the maximal inscribed ellipsoid for a polytope
From MaRDI portal
Publication:1315411
DOI10.1007/BF01582144zbMATH Open0792.90088OpenAlexW2055356142MaRDI QIDQ1315411FDOQ1315411
Authors: Leonid G. Khachiyan, Michael J. Todd 
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
Recommendations
- Improved Complexity for Maximum Volume Inscribed Ellipsoids
- Computing the maximum volume inscribed ellipsoid of a polytopic projection
- Complexity investigations on the ellipsoid algorithm
- Algorithms for Polyhedral Approximation of Multidimensional Ellipsoids
- On the combinatorial complexity of approximating polytopes
- On the combinatorial complexity of approximating polytopes
- Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
- Optimal Bound on the Combinatorial Complexity of Approximating Polytopes
- Approximation of convex bodies by inscribed simplices of maximum volume
- Recursive algorithms for inner ellipsoidal approximation of convex polytopes.
Cites Work
- Title not available (Why is that?)
- A polynomial-time algorithm, based on Newton's method, for linear programming
- Optimal design: Some geometrical aspects of D-optimality
- Über das Löwnersche Ellipsoid und sein Analogon unter den einem Eikörper einbeschriebenen Ellipsoiden
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Potential Reduction Algorithm Allowing Column Generation
- On the complexity of four polyhedral set containment problems
- An Algorithm for Separating Patterns by Ellipsoids
Cited In (36)
- Playing Billiards in Version Space
- Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices
- Sharpening geometric inequalities using computable symmetry measures
- Recursive algorithms for inner ellipsoidal approximation of convex polytopes.
- A portfolio selection model using fuzzy returns
- Interior-point methods: An old and new approach to nonlinear programming
- A cutting plane algorithm for convex programming that uses analytic centers
- Relatively smooth convex optimization by first-order methods, and applications
- Rank-two update algorithms for the minimum volume enclosing ellipsoid problem
- Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids
- On the minimum volume simplex enclosure problem for estimating a linear mixing model
- Conditional minimum volume ellipsoid with application to multiclass discrimination
- Most likely maximum entropy for population analysis with region-censored data
- Minimal ellipsoid circumscribing a polytope defined by a system of linear inequalities
- Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization
- Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method
- Minimum-volume enclosing ellipsoids and core sets
- Symmetry of convex sets and its applications to the extremal ellipsoids of convex bodies
- Approximating fixed points of weakly contracting mappings
- Methods of centers for variational inequalities and linear programming
- Complexity analysis of logarithmic barrier decomposition methods for semi-infinite linear programming
- On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids
- A delimitation of the support of optimal designs for Kiefer's \(\phi _p\)-class of criteria
- Algorithms to construct a minimum-volume invariant ellipsoid for a stable dynamic system
- Finding minimum volume circumscribing ellipsoids using generalized copositive programming
- A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem
- On self-concordant convex–concave functions
- An interior-point smoothing technique for Lagrangian relaxation in large-scale convex programming†
- Clustering via minimum volume ellipsoids
- Accuracy certificates for convex minimization with inexact oracle
- How to solve a design centering problem
- On the complexity of some basic problems in computational convexity. I. Containment problems
- Scientific contributions of Leo Khachiyan (a short overview)
- A modification of the inscribed ellipsoid method
- Inscribed ball and enclosing box methods for the convex maximization problem
- Oracle-polynomial-time approximation of largest simplices in convex bodies
This page was built for publication: On the complexity of approximating the maximal inscribed ellipsoid for a polytope
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1315411)
