Schreiber Building
Computational Geometry Seminar
Wednesday, April 11th, 2007, 16:10-18:00
Room 309
Schreiber Building
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