Improved approximation algorithms for constrained fault-tolerant resource allocation
Journal article
Liao, Kewen, Shen, Hong and Guo, Longkun. (2015). Improved approximation algorithms for constrained fault-tolerant resource allocation. Theoretical Computer Science. 590, pp. 118-128. https://doi.org/10.1016/j.tcs.2015.02.029
Authors | Liao, Kewen, Shen, Hong and Guo, Longkun |
---|---|
Abstract | In Constrained Fault-Tolerant Resource Allocation (FTRA) problem, we are given a set of sites containing facilities as resources and a set of clients accessing these resources. Each site i can open at most facilities with opening cost . Each client j requires an allocation of open facilities and connecting j to any facility at site i incurs a connection cost . The goal is to minimize the total cost of this resource allocation scenario. FTRA generalizes the Unconstrained Fault-Tolerant Resource Allocation () [1] and the classical Fault-Tolerant Facility Location (FTFL) [2] problems: for every site i, does not have the constraint , whereas FTFL sets . These problems are said to be uniform if all 's are the same, and general otherwise. For the general metric FTRA, we first give an LP-rounding algorithm achieving an approximation ratio of 4. Then we show the problem reduces to FTFL, implying the ratio of 1.7245 from [3]. For the uniform FTRA, we provide a 1.52-approximation primal–dual algorithm in time, where n is the total number of sites and clients. |
Keywords | resource allocation; approximation algorithms; LP-rounding; reduction; primal–dual; time complexity |
Year | 2015 |
Journal | Theoretical Computer Science |
Journal citation | 590, pp. 118-128 |
Publisher | Elsevier |
ISSN | 0304-3975 |
Digital Object Identifier (DOI) | https://doi.org/10.1016/j.tcs.2015.02.029 |
Scopus EID | 2-s2.0-84944732001 |
Research or scholarly | Research |
Page range | 118-128 |
Funder | Australian Research Council (ARC) |
Publisher's version | License All rights reserved File Access Level Controlled |
Output status | Published |
Publication dates | |
Online | 23 Feb 2015 |
Publication process dates | |
Accepted | 18 Feb 2015 |
Deposited | 09 Aug 2021 |
ARC Funded Research | This output has been funded, wholly or partially, under the Australian Research Council Act 2001 |
Grant ID | ARC/DP0985063 |
https://acuresearchbank.acu.edu.au/item/8w904/improved-approximation-algorithms-for-constrained-fault-tolerant-resource-allocation
Restricted files
Publisher's version
100
total views0
total downloads0
views this month0
downloads this month