Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center

DOI10.1007/978-3-662-49529-2_33MaRDI QIDQ2802959zbMATH OpenOpenAlexFDO

Authors Cristina G. Fernandes, Samuel P. de Paula, Lehilton L. C. Pedrosa

Publication date 3 May 2016

Published in LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.01721

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Approximation algorithms (68W25)

Abstract: In the k-center problem, given a metric space V and a positive integer k, one wants to select k elements (centers) of V and an assignment from V to centers, minimizing the maximum distance between an element of V and its assigned center. One of the most general variants is the capacitated {alpha}-fault-tolerant k-center, where centers have a limit on the number of assigned elements, and, if {alpha} centers fail, there is a reassignment from V to non-faulty centers. In this paper, we present a new approach to tackle fault tolerance, by selecting and pre-opening a set of backup centers, then solving the obtained residual instance. For the {0,L}-capacitated case, we give approximations with factor 6 for the basic problem, and 7 for the so called conservative variant, when only clients whose centers failed may be reassigned. Our algorithms improve on the previously best known factors of 9 and 17, respectively. Moreover, we consider the case with general capacities. Assuming {alpha} is constant, our method leads to the first approximations for this case. We also derive approximations for the capacitated fault- tolerant k-supplier problem.

Recommendations

• Improved approximation algorithms for capacitated fault-tolerant \(k\)-center
• The fault-tolerant capacitated \(K\)-center problem
• Fault tolerant \(K\)-center problems
• Improved approximation algorithms for constrained fault-tolerant resource allocation
• Improved approximation algorithm for fault-tolerant facility placement
• Improved approximation algorithms for constrained fault-tolerant resource allocation (extended abstract)
• Approximation algorithms for fault tolerant facility allocation
• Approximation algorithms for the fault-tolerant facility placement problem
• Improved approximation algorithms for the robust fault-tolerant facility location problem

Cited in

(7)

• Fault tolerant \(K\)-center problems
• Improved approximation algorithms for capacitated fault-tolerant \(k\)-center
• Tight FPT approximation for constrained k-center and k-supplier
• Constant Factor Approximation for Capacitated k-Center with Outliers
• The fault-tolerant capacitated \(K\)-center problem
• Centrality of trees for capacitated \(k\)-center
• Centrality of trees for capacitated \(k\)-center

This page was built for publication: Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802959)