We consider the problem of computing the outer-radii of point sets. In this problem, we are given integers n, d, k where k ≤ d, and a set P of n points in R~d. The goal is to compute the outer k-radius of P, denoted by R_k(P), which is the minimum, over all (d - k)-dimensional flats F, of max_(p∈ P)d(p, F), where d(p, F) is the Euclidean distance between the point p and flat F. Computing the radii of point sets is a fundamental problem in computational convexity with significantly many applications. The problem admits a polynomial time algorithm when the dimension d is constant. 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 has been known that R_k(P) can be approximated in polynomial time by a factor of (1 + ε), for any ε > 0, when d - k is a fixed constant. A factor of O((log n)~(1/2)) approximation for R_1(P), the width of the point set P, is implied from the results of Nemirovskii et al. [19] and Nesterov [18]. The first approximation algorithm for general k has been proposed by Varadarajan, Venkatesh and Zhang. Their algorithm is based on semidefinite programming relaxation and the Johnson-Lindenstrauss lemma, and it has a performance guarantee of O((log n · log d)~(1/2)). In this paper, we show that R_k(P) can be approximated by a ratio of O((log n)~(1/2)) for any 1 ≤ k ≤ d and thereby improve the ratio of [20] by a factor of O((log d)~(1/2)) that could be as large as O((log n)~(1/2)). This ratio also matches 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.
展开▼
