Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Improved approximation algorithms for constrained fault-tolerant resource allocation
Author: Liao, K.
Shen, H.
Guo, L.
Citation: Proceedings of the 19th International Symposium on Fundamentals of Computation Theory (FCT 2013), 2013 / L. Gąsieniec, F. Wolter (eds.), pp.236-247
Publisher: Springer
Publisher Place: Germany
Issue Date: 2013
Series/Report no.: Lecture Notes in Computer Science, Vol. 8070
ISBN: 9783642401633
ISSN: 0302-9743
Conference Name: International Symposium on Fundamentals of Computation Theory (19th : 2013 : Liverpool, UK)
Statement of
Kewen Liao, Hong Shen, and Longkun Guo
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 R i facilities with opening cost f i . Each client j requires an allocation of r j open facilities and connecting j to any facility at site i incurs a connection cost c ij . The goal is to minimize the total cost of this resource allocation scenario. FTRA generalizes the Unconstrained Fault-Tolerant Resource Allocation (FTRA  ∞ ) [10] and the classical Fault-Tolerant Facility Location (FTFL) [7] problems: for every site i, FTRA  ∞  does not have the constraint R i , whereas FTFL sets R i  = 1. These problems are said to be uniform if all r j ’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 [2]. For the uniform FTRA, we provide a 1.52-approximation primal-dual algorithm in O(n 4) time, where n is the total number of sites and clients.
Keywords: approximation algorithms; automata; graphs; parameterized algorithms; scheduling
Rights: © Springer-Verlag Berlin Heidelberg 2013
RMID: 0020137951
DOI: 10.1007/978-3-642-40164-0_23
Published version:
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.