Minimum-volume enclosing ellipsoids and core sets

P. Kumar, E. Yildirim

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)1-21
Number of pages21
JournalJournal of Optimization Theory and Applications
Volume126
Issue number1
DOIs
Publication statusPublished - 1 Jul 2005

Keywords

  • Approximation algorithms
  • Core sets
  • Löwner ellipsoids

Fingerprint Dive into the research topics of 'Minimum-volume enclosing ellipsoids and core sets'. Together they form a unique fingerprint.

Cite this