Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/83715
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Liao, K. | - |
dc.contributor.author | Shen, H. | - |
dc.contributor.author | Guo, L. | - |
dc.date.issued | 2013 | - |
dc.identifier.citation | Proceedings of the 19th International Symposium on Fundamentals of Computation Theory (FCT 2013), 2013 / L. Gąsieniec, F. Wolter (eds.), pp.236-247 | - |
dc.identifier.isbn | 9783642401633 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.issn | 1611-3349 | - |
dc.identifier.uri | http://hdl.handle.net/2440/83715 | - |
dc.description.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. | - |
dc.description.statementofresponsibility | Kewen Liao, Hong Shen, and Longkun Guo | - |
dc.language.iso | en | - |
dc.publisher | Springer | - |
dc.relation.ispartofseries | Lecture Notes in Computer Science, Vol. 8070 | - |
dc.rights | © Springer-Verlag Berlin Heidelberg 2013 | - |
dc.source.uri | http://www.springer.com/computer/theoretical+computer+science/book/978-3-642-40163-3 | - |
dc.subject | approximation algorithms | - |
dc.subject | automata | - |
dc.subject | graphs | - |
dc.subject | parameterized algorithms | - |
dc.subject | scheduling | - |
dc.title | Improved approximation algorithms for constrained fault-tolerant resource allocation | - |
dc.type | Conference paper | - |
dc.contributor.conference | International Symposium on Fundamentals of Computation Theory (19th : 2013 : Liverpool, UK) | - |
dc.identifier.doi | 10.1007/978-3-642-40164-0_23 | - |
dc.publisher.place | Germany | - |
pubs.publication-status | Published | - |
dc.identifier.orcid | Shen, H. [0000-0002-3663-6591] [0000-0003-0649-0648] | - |
Appears in Collections: | Aurora harvest 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.