Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions

Piyush Kumar, Joseph S. B. Mitchell, Emre Alper Yildirim

Research output: Contribution to conferencePaperpeer-review

Abstract

We study the minimum enclosing ball (MEB) problem for sets of points or balls in high dimensions. Using techniques of second-order cone programming and "core-sets", we have developed (1 + epsilon)-approximation algorithms that perform well in practice, especially for very high dimensions, in addition to having provable guarantees. We prove the existence of core-sets of size O(1/epsilon), improving the previous bound of O(1 + epsilon), and we study empirically how the core-set size grows with dimension. We show that our algorithm, which is simple to implement, results in fast computation of nearly optimal solutions for point sets in much higher dimension than previously computable using exact techniques.
Original languageEnglish
Pages45-55
Number of pages11
Publication statusPublished - 1 Jan 2013
Event 5th Workshop on Algorithm Engineering and Experiments - Baltimore, United States
Duration: 11 Jan 2003 → …

Conference

Conference 5th Workshop on Algorithm Engineering and Experiments
Abbreviated title ALENEX 2003
CountryUnited States
CityBaltimore
Period11/01/03 → …

Keywords

  • INTERIOR-POINT METHODS
  • SUPPORT VECTOR MACHINES
  • CONES

Fingerprint Dive into the research topics of 'Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions'. Together they form a unique fingerprint.

Cite this