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/2006
Entry Accepted: 08/10/2006
Entry Last Modified: 07/28/2006

Modify/Update this entry