Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/57976
Citations | ||
Scopus | Web of Science® | Altmetric |
---|---|---|
?
|
?
|
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Xu, S. | - |
dc.contributor.author | Shen, H. | - |
dc.contributor.editor | Dong, Y. | - |
dc.contributor.editor | Du, D.Z. | - |
dc.contributor.editor | Ibarra, O. | - |
dc.date.issued | 2009 | - |
dc.identifier.citation | Lecture Notes in Artificial Intelligence, 2009 / Dong, Y., Du, D.Z., Ibarra, O. (ed./s), vol.5878 LNCS, pp.689-698 | - |
dc.identifier.isbn | 3642106307 | - |
dc.identifier.isbn | 9783642106309 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.issn | 1611-3349 | - |
dc.identifier.uri | http://hdl.handle.net/2440/57976 | - |
dc.description.abstract | We study the problem of Fault-Tolerant Facility Allocation (FTFA) which is a relaxation of the classical Fault-Tolerant Facility Location (FTFL) problem [1]. Given a set of sites, a set of cities, and corresponding facility operating cost at each site as well as connection cost for each site-city pair, FTFA requires to allocate each site a proper number of facilities and further each city a prespecified number of facilities to access. The objective is to find such an allocation that minimizes the total combined cost for facility operating and service accessing. In comparison with the FTFL problem which restricts each site to at most one facility, the FTFA problem is less constrained and therefore incurs less cost which is desirable in application. In this paper, we consider the metric FTFA problem where the given connection costs satisfy triangle inequality and we present a polynomial-time algorithm with approximation factor 1.861 which is better than the best known approximation factor 2.076 for the metric FTFL problem [2]. | - |
dc.description.statementofresponsibility | Shihong Xu and Hong Shen | - |
dc.language.iso | en | - |
dc.publisher | Springer-Verlag Berlin | - |
dc.relation.ispartofseries | Lecture Notes in Computer Science | - |
dc.rights | © Springer-Verlag Berlin Heidelberg 2009 | - |
dc.source.uri | http://dx.doi.org/10.1007/978-3-642-10631-6_70 | - |
dc.title | The fault-tolerant facility allocation problem | - |
dc.type | Conference paper | - |
dc.contributor.conference | International Symposium on Algorithms and Computation (ISAAC) (16 Dec 2009 - 18 Dec 2009 : Honolulu, HI, USA) | - |
dc.identifier.doi | 10.1007/978-3-642-10631-6_70 | - |
dc.publisher.place | Heidelberger Platz 3 Berlin Germany D-14197 | - |
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.