More Web Proxy on the site http://driver.im/

research-article

Return of the primal-dual: distributed metric facilitylocation

Authors:

Sriram PemmarajuAuthors Info & Claims

PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

Pages 180 - 189

https://doi.org/10.1145/1582716.1582747

Published: 10 August 2009 Publication History

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.

References

[1]

Noga Alon, L&#225;szl&#243; Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567--583, 1986.

Digital Library

[2]

Moses Charikar and Sudipto Guha. Improved combinatorial algorithms for the facility location and k-median problems. In FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, page 378, Washington, DC, USA, 1999. IEEE Computer Society.

Digital Library

[3]

G. Cornuejols, G. Nemhouser, and L. Wolsey. Discrete Location Theory. Wiley, 1990.

[4]

Michael Elkin. Distributed approximation: a survey. SIGACT News, 35(4):40--57, 2004.

Digital Library

[5]

Christian Frank. Algorithms for Sensor and Ad Hoc Networks. Springer, 2007.

[6]

Joachim Gehweiler, Christiane Lammersen, and Christian Sohler. A distributed O(1)-approximation algorithm for the uniform facility location problem. In SPAA '06: Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, pages 237--243, 2006.

Digital Library

[7]

Beat Gfeller and Elias Vicari. A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In PODC '07: Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, pages 53--60, 2007.

Digital Library

[8]

Dorit S. Hochbaum. Heuristics for the fixed cost median problem. Mathematical Programming, 22(1):148--162, 1982.

Digital Library

[9]

Kamal Jain and Vijay V. Vazirani. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM, 48(2):274--296, 2001.

Digital Library

[10]

M. Khan and G. Pandurangan. A fast distributed approximation algorithm for minimum spanning trees. Distributed Computing, 20(6):391--402, 2008.

[11]

Fabian Kuhn and Thomas Moscibroda. Distributed approximation of capacitated dominating sets. In SPAA '07: Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, pages 161--170, New York, NY, USA, 2007. ACM.

Digital Library

[12]

Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. What cannot be computed locally! In PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, pages 300--309, New York, NY, USA, 2004. ACM.

Digital Library

[13]

Fabian Kuhn and Roger Wattenhofer. Constant-time distributed dominating set approximation. In PODC '03: Proceedings of the twenty-second annual symposium on Principles of distributed computing, pages 25--32, New York, NY, USA, 2003. ACM.

Digital Library

[14]

Christoph Lenzen, Yvonne Anne Oswald, and Roger Wattenhofer. What can be approximated locally?: case study: dominating sets in planar graphs. In SPAA '08: Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, pages 46--54, New York, NY, USA, 2008. ACM.

Digital Library

[15]

Jyh-Han Lin and Jeffrey Scott Vitter. e-approximations with minimum packing constraint violation (extended abstract). In STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pages 771--782, 1992.

Digital Library

[16]

M Luby. A simple parallel algorithm for the maximal independent set problem. In STOC '85: Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 1--10, 1985.

Digital Library

[17]

Thomas Moscibroda and Roger Wattenhofer. Facility location: distributed approximation. In PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, pages 108--117, 2005.

Digital Library

[18]

Saurav Pandit and Sriram Pemmaraju. Finding facilities fast. In Proceedings of the 10th International Conference on Distributed Computing and Networks, January 2009.

Digital Library

[19]

David Peleg. Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, 2000.

Digital Library

[20]

David B. Shmoys, &#201;va Tardos, and Karen Aardal. Approximation algorithms for facility location problems (extended abstract). In STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 265--274, 1997.

Digital Library

Cited By

Biabani LPaz A(2024)k-Center Clustering in Distributed ModelsStructural Information and Communication Complexity10.1007/978-3-031-60603-8_5(83-100)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_5
Garimella KDe Francisci Morales GGionis ASozio MBailey JMoffat AAggarwal Cde Rijke MKumar RMurdock VSellis TYu J(2015)Scalable Facility Location for Massive Graphs on Pregel-like SystemsProceedings of the 24th ACM International on Conference on Information and Knowledge Management10.1145/2806416.2806508(273-282)Online publication date: 17-Oct-2015
https://dl.acm.org/doi/10.1145/2806416.2806508
Hegeman JPemmaraju S(2015)Sub-logarithmic distributed algorithms for metric facility locationDistributed Computing10.1007/s00446-015-0243-x28:5(351-374)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/s00446-015-0243-x
Show More Cited By

Index Terms

Return of the primal-dual: distributed metric facilitylocation
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles
        Organizing principles for web applications
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

Improved lower bound for differentially private facility location
Abstract
We consider the differentially private (DP) facility location problem in the so called super-set output setting proposed by Gupta et al. [13]. The current best known expected approximation ratio for an ϵ-DP algorithm is O ( log ⁡ n ϵ ) due to ...
Highlights
- Study facility location problem under differential privacy constraints in the super-set output model.
- Previous best algorithm gave O ( log ⁡ n / ϵ )-approximation and previous lower bound on the approximation ratio was O ( 1 / ϵ ).
Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems
FOCS '99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science

We present approximation algorithms for the metric uncapacitated facility location problem and the metric k-median problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: O(m log m) ...
Primal–Dual Algorithms for Connected Facility Location Problems

We consider the Connected Facility Location problem. We are given a graph $G = (V,E)$ with costs $\{c_e\}$ on the edges, a set of facilities $\F \subseteq V$, and a set of clients $\D \subseteq V$. Facility $i$ has a facility opening cost $f_i$ and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '09: Proceedings of the 28th ACM symposium on Principles of distributed computing

August 2009

356 pages

ISBN:9781605583969

DOI:10.1145/1582716

General Chair:
Srikanta Tirthapura
Iowa State University, USA
,
Program Chair:
Lorenzo Alvisi
The University of Texas at Austin, USA

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '09

Sponsor:

PODC '09: ACM Symposium on Principles of Distributed Computing

August 10 - 12, 2009

AB, Calgary, Canada

Acceptance Rates

PODC '09 Paper Acceptance Rate 27 of 110 submissions, 25%;

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
207
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Biabani LPaz A(2024)k-Center Clustering in Distributed ModelsStructural Information and Communication Complexity10.1007/978-3-031-60603-8_5(83-100)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_5
Garimella KDe Francisci Morales GGionis ASozio MBailey JMoffat AAggarwal Cde Rijke MKumar RMurdock VSellis TYu J(2015)Scalable Facility Location for Massive Graphs on Pregel-like SystemsProceedings of the 24th ACM International on Conference on Information and Knowledge Management10.1145/2806416.2806508(273-282)Online publication date: 17-Oct-2015
https://dl.acm.org/doi/10.1145/2806416.2806508
Hegeman JPemmaraju S(2015)Sub-logarithmic distributed algorithms for metric facility locationDistributed Computing10.1007/s00446-015-0243-x28:5(351-374)Online publication date: 1-Oct-2015
https://dl.acm.org/doi/10.1007/s00446-015-0243-x
Pantazopoulos PKaraliopoulos MStavrakakis I(2014)Distributed Placement of Autonomic Internet ServicesIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2013.18625:7(1702-1712)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.1109/TPDS.2013.186
Keller MPawlik SPietrzk PKarl H(2013)A Local Heuristic for Latency-Optimized Distributed Cloud DeploymentProceedings of the 2013 IEEE/ACM 6th International Conference on Utility and Cloud Computing10.1109/UCC.2013.85(429-434)Online publication date: 9-Dec-2013
https://dl.acm.org/doi/10.1109/UCC.2013.85
Hegeman JPemmaraju S(2013)A Super-Fast Distributed Algorithm for Bipartite Metric Facility LocationDistributed Computing10.1007/978-3-642-41527-2_36(522-536)Online publication date: 2013
https://doi.org/10.1007/978-3-642-41527-2_36
Gehweiler JLammersen CSohler C(2012)A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location ProblemAlgorithmica10.1007/s00453-012-9690-y68:3(643-670)Online publication date: 20-Sep-2012
https://doi.org/10.1007/s00453-012-9690-y
Berns AHegeman JPemmaraju S(2012)Super-fast distributed algorithms for metric facility locationProceedings of the 39th international colloquium conference on Automata, Languages, and Programming - Volume Part II10.1007/978-3-642-31585-5_39(428-439)Online publication date: 9-Jul-2012
https://dl.acm.org/doi/10.1007/978-3-642-31585-5_39
Pantazopoulos PKaraliopoulos MStavrakakis IKalmanek CMedhi D(2011)Centrality-driven scalable service migrationProceedings of the 23rd International Teletraffic Congress10.5555/2043468.2043489(127-134)Online publication date: 6-Sep-2011
https://dl.acm.org/doi/10.5555/2043468.2043489
Kothapalli KPemmaraju SGavoille CFraigniaud P(2011)Distributed graph coloring in a few roundsProceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing10.1145/1993806.1993812(31-40)Online publication date: 6-Jun-2011
https://dl.acm.org/doi/10.1145/1993806.1993812
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents