January 28, Wednesday
12:00 – 14:00
f_1, …, f_n of n continuous functions from R^d to R, we consider the problem of finding a center x* that minimizes OPT
sum_{f in F} f(x*). We present an efficient bi-criteria approximation that returns a small set X such that sum_{fin F}min_{xin X}f(x) exceeds OPT by a factor of no more than (1+eps). The quality of our algorithm (namely, the running time and the size of X) depends on the combinatorial complexity of the set F. I.e., the complexity of the arrangement formed by the functions f_i when viewed as manifolds in R^{d+1}. Given a set of n data elements e_1, …, e_n, a parameter k, and a cost function d(-,-), the ``bi-criteria approximate clustering'' problem addressed the finding of k'>k centers c_1, ..,c_{k'} for which sum_{i=1}^n min_j d(e_i,c_j) is at most (1+eps)-times the optimal k clustering. Bi-criteria approximate clustering stands at the center of several approximation algorithms for clustering and has seen a significant amount of research over the past decade.Defining the function set F appropriately, our algorithm can be applied to obtain bi-criteria approximate clustering in several standard and new clustering settings. These include variants of k-mean clustering, where both the data elements e_i and the centers c_j are points in R^d, and the projective clustering in which the centers c_j are flats (affine subspaces) instead of points. We suggest the first approximation for the generalized projective clustering, where both the data elements e_i and the centers c_j are flats. New settings for which our scheme applies include recovering missing entries in a matrix, solving k-means in the context of missing data, motion analysis, and camera pose estimation. Not only does our framework unify several previous approaches for bi-criteria approximation, in the case of projective clustering it significantly improves the state of the art. Joint work with Michael Langberg.