  


Approximating the Radii of Point Sets
Kasturi Varadarajan (kvaradarcs.uiowa.edu) Abstract: We consider the problem of computing the outerradii 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 $(dk)$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{fksnccjp96}. 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 NPhard 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 (Semidefinite Programming ) Category 3: Applications  Science and Engineering (DataMining ) 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  