Summary: Clustering is a fundamental problem in unsupervised learning. In many real-world applications, the to-be-clustered data often contains various types of noises and thus needs to be removed from the learning process. To address this issue, we consider in this paper two variants of such clustering problems, called \(k\)-median with \(m\) outliers and \(k\)-means with \(m\) outliers. Existing techniques for both problems either incur relatively large approximation ratios or can only efficiently deal with a small number of outliers. In this paper, we present improved solution to each of them for the case where \(k\) is a fixed number and \(m\) could be quite large. Particularly, we gave the first PTAS for the \(k\)-median problem with outliers in Euclidean space \(\mathbb{R}^d\) for possibly high \(m\) and \(d\). Our algorithm runs in \(O\left(nd\left(\frac{1}{\varepsilon}(k+m)\right)^{(\frac{k}{\varepsilon})^{O(1)}}\right)\) time, which considerably improves the previous result (with running time \(O\left(nd(m+k)^{O(m+k)}+ \left(\frac{1}{\varepsilon}k\log n\right)^{O(1)}\right)\) given by [D. Feldman andL. J. Schulman, in: Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1343–1354 (2012;Zbl 1426.62184)]. For the k-means with outliers problem, we introduce a \((6+\varepsilon)\)-approximation algorithm for general metric space with running time \(O\left(n\left(\beta\frac{1}{\varepsilon}(k+m)\right)^k\right)\) for some constant \(\beta>1\). Our algorithm first uses the \(k\)-means\(++\) technique to sample \(O\left(\frac{1}{\varepsilon}(k+m)\right)\) points from input and then select the \(k\) centers from them. Compared to the more involving existing techniques, our algorithms are much simpler, i.e., using only random sampling, and achieving better performance ratios.
For the entire collection see [Zbl 1433.68025].