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 language | English |
---|---|
Pages | 45-55 |
Number of pages | 11 |
Publication status | Published - 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 |
Country/Territory | United States |
City | Baltimore |
Period | 11/01/03 → … |
Keywords / Materials (for Non-textual outputs)
- INTERIOR-POINT METHODS
- SUPPORT VECTOR MACHINES
- CONES