Approximation algorithms for network design problems with restrictions
Coherent Control of Collective Motion and Rydberg-dependent Gates
| Full text | |
| Author(s): |
Fernandes, Cristina G.
;
de Paula, Samuel P.
;
Pedrosa, Lehilton L. C.
Total Authors: 3
|
| Document type: | Journal article |
| Source: | ALGORITHMICA; v. 80, n. 3, p. 32-pg., 2018-03-01. |
| Abstract | |
In the -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 -fault-tolerant k-center, where centers have a limit on the number of assigned elements, and, if any 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 -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 best previously known factors of 9 and 17, respectively. Moreover, we consider the case with general capacities. Assuming is constant, our method leads to the first approximations for this case. We also derive approximations for the capacitated fault-tolerant k-supplier problem. (AU) | |
| FAPESP's process: | 14/14209-1 - Approximation algorithms for network design problems with restrictions |
| Grantee: | Lehilton Lelis Chaves Pedrosa |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |