Fault-Tolerant Center Problems with Robustness and Fairness
share
We study a family of clustering problems that require fault-tolerant solutions that are also robust with the presence of outliers. We consider robust fault-tolerant k-center, matroid center and knapsack center, and develop pure or multi-criteria approximation algorithms for them. In order to address the fairness concern, we also consider variants of the aforementioned problems, namely fair robust fault-tolerant center problems. In these problems, each client j has a value e_j, and we need to stochastically open a set of facilities such that the expected number of facilities that are assigned to j is at least e_j. We develop a pure approximation for fair robust fault-tolerant k-center and multi-criteria approximation algorithms for the knapsack and matroid variations.
READ FULL TEXT