Clustering problems are well studied in a variety of fields, such as data science, operations research, and computer science. Such problems include variants of center location problems, k-median and k-means to name a few. In some cases, not all data points need to be clustered; some may be discarded for various reasons. For instance, some points may arise from noise in a dataset or one might be willing to discard a certain fraction of the points to avoid incurring unnecessary overhead in the cost of a clustering solution. We study clustering problems with outliers. More specifically, we look at uncapacitated facility location (UFL), k-median, and k-means. In these problems, we are given a set X of data points in a metric space δ (., .), a set C of possible centers (each maybe with an opening cost), maybe an integer parameter k, plus an additional parameter z as the number of outliers. In uncapacitated facility location with outliers, we have to open some centers, discard up to z points of X, and assign every other point to the nearest open center, minimizing the total assignment cost plus center opening costs. In k-median and k-means, we have to open up to k centers, but there are no opening costs. In k-means, the cost of assigning j to i is δ 2 (j, i). We present several results. Our main focus is on cases where δ is a doubling metric (this includes fixed dimensional Euclidean metrics as a special case) or is the shortest path metrics of graphs from a minor-closed family of graphs. For uniform-cost UFL with outliers on such metrics, we show that a multiswap simple local search heuristic yields a PTAS. With a bit more work, we extend this to bicriteria approximations for the k-median and k-means problems in the same metrics where, for any constant ϵ > 0, we can find a solution using (1 + ϵ )k centers whose cost is at most a (1 + ϵ )-factor of the optimum and uses at most z outliers. Our algorithms are all based on natural multiswap local search heuristics. We also show that natural local search heuristics that do not violate the number of clusters and outliers for k-median (or k-means) will have unbounded gap even in Euclidean metrics. Furthermore, we show how our analysis can be extended to general metrics for k-means with outliers to obtain a (25 + ϵ, 1 + ϵ )-approximation: an algorithm that uses at most (1 + ϵ )k clusters and whose cost is at most 25 + ϵ of optimum and uses no more than z outliers. A preliminary version of this article appeared Clustering is the task of partitioning a given set of data points into clusters based on a specified similarity measure between the data points such that the points within the same cluster are more similar to each other than those in different clusters. In a typical clustering problem, we are given a set of n data points in a metric space and an integer k that specifies the desired number of clusters. We wish to find a set of k points to act as centers and then assign each point to its nearest center, thereby forming k clusters. The quality of the clustering solution can be measured by using different objectives. For example, in the k-means clustering (which is the most widely used clustering model), the goal (objective function) is to minimize the sum of squared distances of each data point to its center, while in k-median, the goal is to minimize the sum of distances of each data point to its center. The uncapacitated facility location problem is the same as k-median except that instead of a cardinality constraint bounding the number of centers, there is an additional cost for each center included in the solution. Minimizing these objective functions exactly is NP-hard [3, 19, 24, 32, 42, 46] , so there has been substantial work on obtaining provable upper bounds (approximability) and lower bounds (inapproximability) for these objectives; see References [1, 11, 24, 32, 38, 39] for the currently best bounds. Although inapproximability results [24, 32, 38] prevent getting polynomial time approximation schemes (PTASs) for these problems in general metrics, PTASs are known for these problems in fixed dimensional Euclidean metrics [5, 17, 22] . Indeed, PTASs for k-median and uncapacitated facility location in fixed dimension Euclidean space [5] have been known for almost two decades, but getting a PTAS for k-means in fixed dimension Euclidean space had been an open problem until recent results in References [17, 22] . In spite of the fact that these popular (center-based) clustering models are reasonably good for noise-free datasets, their objective functions (specially the k-means objective function) are extremely sensitive to the existence of points far from cluster centers. Therefore, a small number of very distant data points, called outliers-if not discarded-can dramatically affect the clustering cost and also the quality of the final clustering solution. Dealing with such outliers is indeed the main focus of this article. Clustering with outliers has a natural motivation in applications where outliers and unexpected data contained in the data may apply a strong influence over the clustering quality. In some specific applications, we need to find out the anomaly patterns (outliers) in the data for further investigation [29] . This finds applications, for example, in detecting fraudulent usage of credit cards-by monitoring transactions data to detect exceptional cases perhaps in type of purchase, location, timeframe, and so on-or in detecting suspicious trades in the equity markets or in monitoring medical condition or more; see Reference [29] for more details. We restrict our attention to the outlier version of the three well-studied clustering problems: kmeans with outliers (k-means-out), k-median with outliers (k-median-out), and uncapacitated facility location with outliers (UFL-out). Formally, in these problems, we are given a set X of
More recently, Friggstad et al. REF showed that local search provides a bicriteria approximation, where the number of centers is approximate instead of the number of outliers.
Approximation Schemes for Clustering with Outliers
TALG
Computer Science Mathematics