Open Collections

Approximation Schemes for Clustering Problems: Now With Outliers

Banff International Research Station for Mathematical Innovation and Discovery

Recent developments in local search analysis have yielded the first polynomial-time approximation schemes for the k-Means, k-Median, and Uncapacitated Facility Location problems (among others) in a variety of specific classes of metrics . An important extension of these problems is to the setting with outliers. That is, we we are given an additional parameter Z and may discard up to Z points/clients in the input. This is especially important in the setting of k-Means clustering where even a small fraction of outliers may cause a noticeable deviation in the centroids of near-optimum solutions. I will start with a brief review of our work from last year in local search analysis for k-Means clustering in Euclidean metrics. Then I will present a more recent development: a general framework for adapting local search analysis for clustering problems to get approximations for their variants with outliers. In particular, we obtain the following results for clustering in doubling metrics (including constant-dimensional Euclidean metrics) and shortest path metrics of bounded genus graphs. 1) PTASes for uniform opening cost UFL with outliers and 2) bicriteria PTASes that open (1+eps)*k centres for k-Median and k-Means clustering with outliers. There is no violation on the given bound for outliers in any of these approximations. This is joint work with Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R. Salavatipour.

Mathematics; Computer science; Operations research, mathematical programming; Theoretical computer science

video/mp4

Author affiliation: University of Alberta

2018-05-16

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/65912

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/