- Approximating the Radii of Point Sets Kasturi Varadarajan (kvaradarcs.uiowa.edu) S Venkatesh ( venkatcs.uvic.ca) Yinyu Ye (yinyu-yestanford.edu) Zhang Jiawei (jzhangstern.nyu.edu) Abstract: We consider the problem of computing the outer-radii of point sets. In this problem, we are given integers $n, d, k$ where $k \le d$, and a set $P$ of $n$ points in $R^d$. The goal is to compute the {\em outer $k$-radius} of $P$, denoted by $\kflatr(P)$, which is the minimum, over all $(d-k)$-dimensional flats $\FLAT$, of $\max_{p \in P} d(p,\FLAT)$, where $d(p,\FLAT)$ is the Euclidean distance between the point $p$ and flat $\FLAT$. Computing the radii of point sets is a fundamental problem in computational convexity with many significant applications. The problem admits a polynomial time algorithm when the dimension $d$ is constant \cite{fks-nccjp-96}. Here we are interested in the general case when the dimension $d$ is not fixed and can be as large as $n$, where the problem becomes NP-hard even for $k=1$. It is known that $\kflatr(P)$ can be approximated in polynomial time by a factor of $(1 + \eps)$, for any $\eps > 0$, when $d - k$ is a fixed constant. A polynomial time algorithm that guarantees a factor of $O(\sqrt{\log n})$ approximation for $R_1(P)$, the width of the point set $P$, is implied by the results of Nemirovski et al. and Nesterov. In this paper, we show that $R_k(P)$ can be approximated by a ratio of $O(\sqrt{\log n})$ for any $1 \leq k \leq d$, thus matching the previously best known ratio for approximating the special case $R_1 (P)$, the width of point set $P$. Our algorithm is based on semidefinite programming relaxation with a new mixed deterministic and randomized rounding procedure. We also prove an inapproximability result for computing $\kflatr(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 $\kflatr(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. Keywords: radii of point sets, semidefinite programming Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming ) Category 3: Applications -- Science and Engineering (Data-Mining ) Citation: Working Paper posted 5/4/05; conference versions appeared in FOCS'02 and APPROX'04; full paper to appear in SIAM Journal on Computing. Download: [PDF]Entry Submitted: 07/28/2006Entry Accepted: 08/10/2006Entry Last Modified: 07/28/2006Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.