Please use this identifier to cite or link to this item: https://hdl.handle.net/2440/70161
Scopus Web of Science® Citations ? ?
DC FieldValueLanguage
dc.contributor.authorXu, S.-
dc.contributor.authorShen, H.-
dc.date.issued2011-
dc.identifier.citationInternational Journal of Foundations of Computer Science, 2011; 22(5):1019-1034-
dc.identifier.issn0129-0541-
dc.identifier.issn1793-6373-
dc.identifier.urihttp://hdl.handle.net/2440/70161-
dc.description.abstractIn this paper, we propose an approximation algorithm for the Fault-Tolerant Metric Facility Location problem which can be implemented in a distributed and asynchronous manner within O(n) rounds of communication, where n is the number of vertices in the network. Given a constant size set $\mathcal{R}$ which represents distinct levels of fault-tolerant requirements of all cities, as well as the two-part (facility and connection) cost of the optimal solution, i.e. F* + C*, the cost of our solution is no more than $|\mathcal{R}|\, \cdot \,F^* \, + \,2C^*$ for the general case, and less than F* + 2C* for the special case where all cities have a uniform connectivity requirement. Extensive numerical experiments showed that the quality of our solutions is comparable (within 4% error) to the optimal solution in practice.-
dc.description.statementofresponsibilityShihong Xu and Hong Shen-
dc.language.isoen-
dc.publisherWorld Scientific Publishing Co. Pte. Ltd.-
dc.rightsCopyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company-
dc.subjectApproximation algorithms-
dc.subjectdistributed algorithms-
dc.subjectfault tolerance-
dc.subjectmetric facility location problem-
dc.titleA distributed approximation algorithm for fault-tolerant metric facility location-
dc.typeJournal article-
dc.identifier.doi10.1142/S0129054111008544-
dc.relation.granthttp://purl.org/au-research/grants/arc/DP0985063-
pubs.publication-statusPublished-
dc.identifier.orcidShen, 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.