Computing minimum-volume enclosing axis-aligned ellipsoids

P. Kumar, E. A. Yıldırım*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Given a set of points S = {x 1 ,..., x m }⊂ ℝ n and ε>0, we propose and analyze an algorithm for the problem of computing a (1+ε)-approximation to the minimum-volume axis-aligned ellipsoid enclosing S. We establish that our algorithm is polynomial for fixed ε. In addition, the algorithm returns a small core set X ⊆ S, whose size is independent of the number of points m, with the property that the minimum-volume axis-aligned ellipsoid enclosing X is a good approximation of the minimum-volume axis-aligned ellipsoid enclosing S. Our computational results indicate that the algorithm exhibits significantly better performance than the theoretical worst-case complexity estimate.

Original languageEnglish
Pages (from-to)211-228
Number of pages18
JournalJournal of Optimization Theory and Applications
Volume136
Issue number2
DOIs
Publication statusPublished - 1 Jan 2008

Keywords

  • Approximation algorithms
  • Axis-aligned ellipsoids
  • Core sets
  • Enclosing ellipsoids

Fingerprint

Dive into the research topics of 'Computing minimum-volume enclosing axis-aligned ellipsoids'. Together they form a unique fingerprint.

Cite this