Computational Geometry Seminar

Wednesday, April 11th, 2007, 16:10-18:00

Room 309
Schreiber Building

Bi-criteria Linear-time Approximations for Generalized k-Mean/Median/Center

Dan Feldman, Tel Aviv University


We consider the problem of approximating a set P of n points in R^d by a collection of j-dimensional flats, and extensions thereof, under the standard median / mean / center measures, in which we wish to minimize, respectively, the sum of the distances from each point of P to its nearest flat, the sum of the squares of these distances, or the maximal such distance. Such problems cannot be approximated unless P=NP but do allow bi-criteria approximations where one allows some leeway in both the number of flats and the quality of the objective function. We give a very simple bi-criteria approximation algorithm, which produces at most alpha(k,j,n) = log n*(jk loglog n)^O(j) flats, which exceeds the optimal objective value for any k j-dimensional flats by a factor of no more than \beta(j)= 2^O(j). Given this bi-criteria approximation, we can use it to reduce the approximation factor arbitrarily, at the cost of increasing the number of flats. Our algorithm has many advantages over previous work, in that it is much more widely applicable (wider set of objective functions and classes of clusters) and much more efficient --- reducing the running time bound from O(n^{\poly(k,j)}) to dn*(jk)^O(j). Our algorithm is randomized and successful with probability 1/2 (easily boosted to probabilities arbitrarily close to 1).

A joint work with Amos Fiat, Micha Sharir, and Danny Segev