2023/10/11 by Deeparnab Chakrabarty, Chakrabarty, Deeparnab, L. Côté +3 · 1 citation
Business, Management and Accounting · Computer Science · Decision Sciences · #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Facility Location and Emergency Management #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2310.07208
openalex publication_date 2023/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present approximation algorithms for the Fault-tolerant k-Supplier with Outliers (FkSO) problem. This is a common generalization of two known problems -- k-Supplier with Outliers, and Fault-tolerant k-Supplier -- each of which generalize the well-known k-Supplier problem. In the k-Supplier problem the goal is to serve n clients C, by opening k facilities from a set of possible facilities F; the objective function is the farthest that any client must travel to access an open facility. In FkSO, each client v has a fault-tolerance ℓv, and now desires ℓv facilities to serve it; so each client v's contribution to the objective function is now its distance to the ℓvth closest open facility. Furthermore, we are allowed to choose m clients that we will serve, and only those clients contribute to the objective function, while the remaining n-m are considered outliers. Our main result is a min\4t-1,2t+1\-approximation for the FkSO problem, where t is the number of distinct values of ℓv that appear in the instance. At t=1, i.e. in the case where the ℓv's are uniformly some ℓ, this yields a 3-approximation, improving upon the 11-approximation given for the uniform case by Inamdar and Varadarajan [2020], who also introduced the problem. Our result for the uniform case matches tight 3-approximations that exist for k-Supplier, k-Supplier with Outliers, and Fault-tolerant k-Supplier. Our key technical contribution is an application of the round-or-cut schema to FkSO. Guided by an LP relaxation, we reduce to a simpler optimization problem, which we can solve to obtain distance bounds for the "round" step, and valid inequalities for the "cut" step.