On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids

Michael J. Todd, E. Alper Yıldırım

Type: Article

Publication Date: 2007-04-06

Citations: 201

DOI: https://doi.org/10.1016/j.dam.2007.02.013

View Publication

Locations

Discrete Applied Mathematics - View
eCommons (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	On the Minimum Volume Covering Ellipsoid of Ellipsoids	2006	E. Alper Yıldırım
+	Approximate Minimum Volume Enclosing Ellipsoids Using Core Sets	2003	Piyush Kumar E. Alper Yıldırım
+ PDF Chat	Computing Minimum-Volume Enclosing Axis-Aligned Ellipsoids	2007	Piyush Kumar E. Alper Yıldırım
+	Ellipsoidal approximations of convex sets based on the volumetric barrier	1997	Kurt M. Anstreicher
+ PDF Chat	Minkowski Centers via Robust Optimization: Computation and Applications	2023	Dick den Hertog Jean Pauphilet Mohamed Yahya Soali
+	Computing the Maximum Volume Inscribed Ellipsoid of a Polytopic Projection	2017	Jianzhe Zhen Dick den Hertog
+	An algorithmic separating hyperplane theorem and its applications	2018	Bahman Kalantari
+	On Minimum Volume Ellipsoids Containing Part of a Given Ellipsoid	1982	Michael J. Todd
+ PDF Chat	Identification and Elimination of Interior Points for the Minimum Enclosing Ball Problem	2008	Selin Damla Ahipaşaoğlu E. Alper Yıldırım
+	Optimal Area-Sensitive Bounds for Polytope Approximation	2023	Sunil K. Arya Guilherme D. da Fonseca David M. Mount
+	On Chebyshev Center of the Intersection of Two Ellipsoids	2019	Xiaoli Cen Yong Xia Runxuan Gao Tianzhi Yang
+	A O(1/eps^2)^n Time Sieving Algorithm for Approximate Integer Programming	2011	Daniel Dadush
+	Karmarkar's algorithm and the ellipsoid method	1987	Yinyu Ye
+	Optimal Volume-Sensitive Bounds for Polytope Approximation	2023	Sunil K. Arya David M. Mount
+	Improved Complexity for Maximum Volume Inscribed Ellipsoids	2002	Kurt M. Anstreicher
+	Concave minimization via conical partitions and polyhedral outer approximation	1991	Reiner Horst Nguyễn Văn Thoại Harold P. Benson
+	New Approximation Algorithms for Minimum Enclosing Convex Shapes	2009	Ankan Saha S. V. N. Vishwanathan Xinhua Zhang
+ PDF Chat	New Approximation Algorithms for Minimum Enclosing Convex Shapes	2011	Ankan Saha S. V. N. Vishwanathan Xinhua Zhang
+	Using Optimization to Find Maximum Inscribed Balls and Minimum Enclosing Balls	2014	Zeyuan Allen Zhu Zhenyu Liao Lorenzo Orecchia
+	Contribution to the Ellipsoid Algorithm	1980	Lenore Blum Péter Gács Leonid A. Levin

Works That Cite This (74)

Action	Title	Year	Authors
+	Measuring centrality and dispersion in directional datasets: the ellipsoidal cone covering approach	2016	Alberto Seeger José Vidal-Núñez
+ PDF Chat	Markov inequalities, Dubiner distance, norming meshes and polynomial optimization on convex bodies	2019	Federico Piazzon Marco Vianello
+	Global linear convergent algorithm to compute the minimum volume enclosing ellipsoid	2017	Tao Jie Wei Zhang Chao Lu
+	Uniqueness results for minimal enclosing ellipsoids	2008	Hans-Peter Schröcker
+ PDF Chat	Extremal general affine surface areas	2021	Steven Hoehner
+	A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si20.gif" display="inline" overflow="scroll"><mml:msup><mml:mrow><mml:mn>2</mml:mn></mml:mrow><mml:mrow><mml:mi>O</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>log</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo></mml:mrow></mml:mrow></mml:msup></mml:math>	2012	Robert Hildebrand Matthias Köppe
+ PDF Chat	Ellipsoids for anomaly detection in remote sensing imagery	2015	Guenchik Grosklos James Theiler
+ PDF Chat	Scalable Zonotope-Ellipsoid Conversions using the Euclidean Zonotope Norm	2020	Victor Gasmann Matthias Althoff
+	Overlap of convex polytopes under rigid motion	2013	Hee-Kap Ahn Siu-Wing Cheng Hyuk Jun Kweon Juyoung Yon
+	An Evolutionary Approach to Constructing the Minimum Volume Ellipsoid Containing a Set of Points and the Maximum Volume Ellipsoid Embedded in a Set of Points	2020	Rewayda Abo-Alsabeh Abdellah Salhi

Works Cited by This (19)

Action	Title	Year	Authors
+	None	1999	Kim-Chuan Toh
+	Extremum Problems with Inequalities as Subsidiary Conditions	2013	Fritz John
+	A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio	1993	Ilan Adler Ron Shamir
+ PDF Chat	On Numerical Solution of the Maximum Volume Ellipsoid Problem	2003	Yin Zhang L. Gao
+	On self-concordant convex–concave functions	1999	Arkadi Nemirovski
+ PDF Chat	Determinant Maximization with Linear Matrix Inequality Constraints	1998	Lieven Vandenberghe Stephen Boyd Shao-Po Wu
+	Improved Complexity for Maximum Volume Inscribed Ellipsoids	2002	Kurt M. Anstreicher
+	Some comments on Wolfe's ‘away step’	1986	J Guelat Patrice Marcotte
+	On Minimum Volume Ellipsoids Containing Part of a Given Ellipsoid	1982	Michael J. Todd
+	Modifications and implementation of the ellipsoid algorithm for linear programming	1982	Donald Goldfarb Michael J. Todd