- | ||||
|
![]()
|
Approximating the Radii of Point Sets
Kasturi Varadarajan (kvaradar 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 Modify/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 | |
![]() |