Special Issue — International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2009)No Access

A DISTRIBUTED APPROXIMATION ALGORITHM FOR FAULT-TOLERANT METRIC FACILITY LOCATION

SHIHONG XU

School of Computer Science, University of Adelaide, Adelaide, SA 5005, Australia

Search for more papers by this author

and

HONG SHEN

School of Computer Science, University of Adelaide, Adelaide, SA 5005, Australia

Search for more papers by this author

https://doi.org/10.1142/S0129054111008544Cited by:0 (Source: Crossref)

Abstract

In 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 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 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.

Keywords:

References

J. Byrka , An optimal bifactor approximation algorithm for the metric uncapacited facility location problem , APPROX and RANDOM 2007 ( 2007 ) . Google Scholar
K. L. Calvert, M. B. Doar and E. W. Zegura, IEEE Comm. Magazine 35(6), 160 (1997), DOI: 10.1109/35.587723. Crossref, Web of Science, Google Scholar
M. Charikar and S. Guha, SIAM J. Comput. 34(4), 803 (2005), DOI: 10.1137/S0097539701398594. Crossref, Web of Science, Google Scholar
G. Cornuejols, M. L. Fisher and G. L. Nemhauser, Management Science 23(8), 789 (1977), DOI: 10.1287/mnsc.23.8.789. Crossref, Web of Science, Google Scholar
C. Frank and K. Römer , Distributed facility location algorithms for flexible configuration of wireless sensor networks , Proceedings of the 3rd IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS 2007) . Google Scholar
J. Gehweiler, C. Lammersen and C. Sohler, A distributed o(1)-approximation algorithm for the uniform facility location problem, SPAA '06: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures (ACM, New York, NY, USA, 2006) pp. 237–243. Google Scholar
S. Guha, A. Meyerson and K. Munagala, Improved algorithms for fault tolerant facility location, SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms (Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2001) pp. 636–641. Google Scholar
S. Guha, A. Meyerson and K. Munagala, J. Algorithms 48(2), 429 (2003), DOI: 10.1016/S0196-6774(03)00056-7. Crossref, Web of Science, Google Scholar
S. Guha, A. Meyerson and K. Munagala, J. Algorithms 48(2), 429 (2003), DOI: 10.1016/S0196-6774(03)00056-7. Crossref, Web of Science, Google Scholar
D. S. Hochbaum, Mathematical Programming 22(1), 148 (1982), DOI: 10.1007/BF01581035. Crossref, Web of Science, Google Scholar
K. Jainet al., Journal of the ACM 50(6), 795 (2003), DOI: 10.1145/950620.950621. Crossref, Web of Science, Google Scholar
K. Jain, M. Mahdian and A. Saberi, A new greedy approach for facility location problems, STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (ACM, New York, NY, USA, 2002) pp. 731–740. Google Scholar
K. Jain and V. V. Vazirani, An approximation algorithm for the fault tolerant metric facility location problem, APPROX '00: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization (Springer-Verlag, London, UK, 2000) pp. 177–183. Google Scholar
J.-H. Lin and J. S. Vitter, e-approximations with minimum packing constraint violation (extended abstract), STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing (ACM, New York, NY, USA, 1992) pp. 771–782. Google Scholar
M. Mahdian, Y. Ye and J. Zhang, A 1.52-approximation algorithm for the uncapacitated facility location problem, Proc. of APPROX 2002, LNCS 2462 (2002) pp. 229–242. Google Scholar
A. S. V. V. Mohammad Mahdian and Evangelos Markakis, A greedy facility location algorithm analyzed using dual fitting, Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (2001) pp. 127–137. Google Scholar
T. Moscibroda and R. Wattenhofer, Facility location: distributed approximation, PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing (ACM, New York, NY, USA, 2005) pp. 108–117. Google Scholar
(eds.) , Discrete Location Theory ( John Wiley , New York , 1990 ) . Google Scholar
Journal of Algorithms 31(21), 228 (1999), DOI: 10.1006/jagm.1998.0993. Crossref, Web of Science, Google Scholar
D. B. Shmoys, E. Tardos and K. Aardal, Approximation algorithms for facility location problems, Proceedings of the 29th Annual ACM Symposium on Theory of Computing (1997) pp. 265–274. Google Scholar
C. Swamy and D. B. Shmoys, ACM Trans. Algorithms 4(4), 1 (2008), DOI: 10.1145/1383369.1383382. Crossref, Web of Science, Google Scholar
S. Xu and H. Shen , Qos-oriented content delivery in e-learning systems , 2009 IEEE International Symposium on IT in Medicine & Education . Google Scholar
E. Zegura, K. Calvert and S. Bhattacharjee, How to model an internetwork, Proceedings of IEEE INFOCOM (1996) pp. 594–602. Google Scholar