Abstract
We study the problem of computing a (1+ε)-approximation to the minimum-volume enclosing ellipsoid of a given point set S = { p 1, p 2,..., p n} ⊆ ℝ d. Based on a simple initial volume approximation method we propose a modification of the Khachiyan first-order algorithm. Our analysis leads to a slightly improved complexity bound of O(nd 3/ε) operations for ε ∈ (0 1). As a byproduct our algorithm returns a core set χ ⊆ S with the property that the minimum-volume enclosing ellipsoid of χ provides a good approximation to that of S. Furthermore the size of χ depends on only the dimension d and ε but not on the number of points n. In particular our results imply that |χ| = O(d 2/ε for ε ∈(0 1).
Original language | English |
---|---|
Pages (from-to) | 1-21 |
Number of pages | 21 |
Journal | Journal of Optimization Theory and Applications |
Volume | 126 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jul 2005 |
Keywords / Materials (for Non-textual outputs)
- Approximation algorithms
- Core sets
- Löwner ellipsoids