Optimization Online


Approximating the Radii of Point Sets

Kasturi Varadarajan (kvaradar***at***cs.uiowa.edu)
S Venkatesh ( venkat***at***cs.uvic.ca)
Yinyu Ye (yinyu-ye***at***stanford.edu)
Zhang Jiawei (jzhang***at***stern.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society