Conference proceeding
Return of the primal-dual: distributed metric facilitylocation
Proceedings of the 28th ACM symposium on principles of distributed computing, pp.180-189
PODC '09
08/10/2009
DOI: 10.1145/1582716.1582747
Abstract
In this paper we present fast, distributed approximation algorithms for the metric facility location problem in the CONGEST model, where message sizes are bounded by O (log N ) bits, N being the network size. We first show how to obtain a 7-approximation in O (log m + log n ) rounds via the primal-dual method; here m is the number of facilities and n is the number of clients. Subsequently, we generalize this to a k -round algorithm, that for every constant k , yields an approximation factor of O ( m 2/√ k ∙ n 3/√ k ). These results answer a question posed by Moscibroda and Wattenhofer ( PODC 2005 ). Our techniques are based on the primal-dual algorithm due to Jain and Vazirani ( JACM 2001 ) and a rapid randomized sparsification of graphs due to Gfeller and Vicari ( PODC 2007 ). These results complement the results of Moscibroda and Wattenhofer ( PODC 2005 ) for non-metric facility location and extend the results of Gehweiler et al. ( SPAA 2006 ) for uniform metric facility location.
Details
- Title: Subtitle
- Return of the primal-dual: distributed metric facilitylocation
- Creators
- Saurav Pandit - University of IowaSriram Pemmaraju - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the 28th ACM symposium on principles of distributed computing, pp.180-189
- Series
- PODC '09
- DOI
- 10.1145/1582716.1582747
- Publisher
- ACM
- Language
- English
- Date published
- 08/10/2009
- Academic Unit
- Computer Science
- Record Identifier
- 9984259488902771
Metrics
14 Record Views