Fault Tolerant Clustering with Outliers In a clustering with outliers problem, we are required to cluster all but a specified number of points, called outliers. In a fault tolerant clustering problem, the objective function incorporates the distance of a point to its fth closest center chosen in the solution. We combine these two orthogonal generalizations, and consider Fault Tolerant Clustering with Outliers problems for various clustering objectives, such as kcenter, kmedian, and sum of radii. We essentially reduce the Fault Tolerant Clustering with Outliers problem, to the corresponding (non Fault Tolerant) Clustering with Outliers problem, for which constant approximations are known. This can be seen as a generalization of the framework of Kumar and Raichel 20 to handle the presence of outliers. This reduction comes at a loss in the approximation guarantee; however, we show that it is bounded by O(1) for the kcenter objective, whereas it is O(f) for kmedian and sum of radii objectives, where f is the degree of Fault Tolerance required in the solution. This implies O(1) and O(f) approximations for these generalizations respectively.

A Binary Linear ProgrammingBased KMeans Approach for the Capacitated Centered Clustering Problem The kmeans algorithm is one of the most popular clustering algorithms in the machine learning community. Its simplicity and scalability make it the primary choice for many clustering applications. We introduce here a variant of the kmeans algorithm that can account for complex side constraints. The key idea is to use binary linear programming for assigning objects to clusters. Unlike existing extensions of the kmeans algorithm that are designed for accommodating specific types of constraints, our approach can be applied to a wide range of constrained clustering problems with minor modifications. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it to a stateoftheart algorithm on a test set that comprises 18 instances of the capacitated centered clustering problem. The proposed approach performed particularly well on largesized instances with more than 100 clusters. It even found new bestknown solutions for the four largest instances in the test set.