Book chapter
Fault Tolerant Clustering with Outliers
Approximation and Online Algorithms, pp.188-201
Lecture Notes in Computer Science, Springer International Publishing
01/25/2020
DOI: 10.1007/978-3-030-39479-0_13
Abstract
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 f-th 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 k-center, k-median, 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 k-center objective, whereas it is O(f) for k-median 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.
Details
- Title: Subtitle
- Fault Tolerant Clustering with Outliers
- Creators
- Tanmay Inamdar - University of IowaKasturi Varadarajan - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Approximation and Online Algorithms, pp.188-201
- Publisher
- Springer International Publishing; Cham
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-030-39479-0_13
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 01/25/2020
- Academic Unit
- Computer Science
- Record Identifier
- 9984259416602771
Metrics
17 Record Views