Conference proceeding
On approximating the radii of point sets in high dimensions
Annual Symposium on Foundations of Computer Science, pp.561-569
FOCS 2002 : foundations of computer science (Vancouver BC, 16-19 November 2002)
2002
DOI: 10.1109/SFCS.2002.1181980
Abstract
Let P be a set of n points in /spl Ropf//sup d/. For any 1/spl les/k/spl les/d, the outer k-radius of P, denoted by R/sub k/(P), is the minimum, over all (d-k) -dimensional fiats F, of max/sub p/spl isin/P/ d(p, F), where d(p, F) is the Euclidean distance between the point p and fiat F. We consider the scenario when the dimension d is not fixed and can be as large as n. Computing the various radii of point sets is a fundamental problem in computational convexity with many applications. The main result of this paper is a randomized polynomial time algorithm that approximates Rk (P) to within a factor of O/spl radic/(log n/spl middot/log d) for any 1/spl les/k/spl les/d. This algorithm is obtained using techniques from semidefinite programming and dimension reduction. Previously, good approximation algorithms were known only for the case k=1 and for the case when k=d-c for any constant c; there are polynomial time algorithms that approximate Rk(P) to within a factor of (1+/spl epsi/), for any /spl epsi/>0, when d-k is any fixed constant. On the other hand, some results from the mathematical programming community on approximating certain kinds of quadratic programs imply an O/spl radic/(log n) approximation for R/sub 1/ (P), the width of the point set P. We also prove an inapproximability result for computing Rk (P), which easily yields the conclusion that our approximation algorithm performs quite well for a large range of values of k. Our inapproximability result for Rk (P) improves the previous known hardness result of Brieden, and is proved by improving the parameters in Brieden's construction using basic ideas from PCP theory.
Details
- Title: Subtitle
- On approximating the radii of point sets in high dimensions
- Creators
- Kasturi R Varadarajan - University of IowaS Venkatesh - Rutgers, The State University of New JerseyJiawei Zhang - Stanford University
- Resource Type
- Conference proceeding
- Publication Details
- Annual Symposium on Foundations of Computer Science, pp.561-569
- Conference
- FOCS 2002 : foundations of computer science (Vancouver BC, 16-19 November 2002)
- Publisher
- IEEE
- DOI
- 10.1109/SFCS.2002.1181980
- ISSN
- 0272-5428
- Language
- English
- Date published
- 2002
- Academic Unit
- Computer Science
- Record Identifier
- 9984259486702771
Metrics
3 Record Views