Article

Facility location: distributed approximation

Authors:

Thomas Moscibroda,

Rogert WattenhoferAuthors Info & Claims

PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

Pages 108 - 117

https://doi.org/10.1145/1073814.1073834

Published: 17 July 2005 Publication History

Abstract

In this paper, we initiate the study of the approximability of the facility location problem in a distributed setting. In particular, we explore a trade-off between the amount of communication and the resulting approximation ratio. We give a distributed algorithm that, for every constant k, achieves an O(√k(mρ)^1/√klog(m+n)) approximation in O(k) communication rounds where message size is bounded to O(log n) bits. The number of facilities and clients are $m$ and n, respectively, and ρ is a coefficient that depends on the cost values of the instance. Our technique is based on a distributed primal-dual approach for approximating a linear program, that does not form a covering or packing program.

References

[1]

B. Awerbuch. Complexity of Network Synchronization. Journal of the ACM, 32(4):804--823, 1985.

Digital Library

[2]

M. L. Balinski. On Finding Integer Solutions to Linear Programs. In Proceedings of the IBM Scientific Computing Symposium on Combinatorial Problems, pages 225--248, 1966.

[3]

Y. Bartal, J. W. Byers, and D. Raz. Global Optimization Using Local Information with Applications to Flow Control. In Proc. 38th Symposium on Foundations of Computer Science (FOCS), pages 303--312, 1997.

Digital Library

[4]

G. Cornuejols, G. Nemhauser, and L. Wolsey. Discrete Location Theory, chapter The Uncapacitated Facility Location Problem, pages 119--171. Wiley, 1990.

[5]

M. Elkin. An Unconditional Lower Bound on the Hardness of Approximation of Distributed Minimum Spanning Tree Problem. In Proceedings of the 36th annual ACM Symposium on Theory of Computing (STOC), pages 331--340, 2004.

Digital Library

[6]

M. Elkin. Distributed Approximation - A Survey. ACM SIGACT News - Distributed Computing Column, 35(4), 2004.

Digital Library

[7]

U. Feige. A Threshold of ln n for Approximating Set Cover. Journal of the ACM, 45(4):634--652, 1998.

Digital Library

[8]

M. X. Goemans and D. P. Williamson. A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput., 24(2):296--317, 1995.

Digital Library

[9]

M. T. Hajiaghayi, M. Mahdian, and V. S. Mirrokni. The Facility Location Problem with General Cost Functions. Networks, 42(1):42--47, 2003.

[10]

W. R. Heinzelman, A. Chandrakasan, and H. Balakrishnan. Energy-Efficient Communication Protocol for Wireless Microsensor Networks. In Proc. 33rd Hawaii International Conference on System Sciences (HICSS), page 8020, 2000.

Digital Library

[11]

D. S. Hochbaum. Heuristics for the fixed cost median problem. Math. Programming, 22:148--162, 1982.

Digital Library

[12]

K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani. Greedy Facility Location Algorithms analyzed using Dual Fitting with Factor-Revealing LP. Journal of the ACM, 50(6):795--824, 2003.

Digital Library

[13]

K. Jain and V. V. Vazirani. Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems. In Proceedings of the 40th Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 1999.

Digital Library

[14]

M. R. Korupolu, C. G. Plaxton, and R. Rajaraman. Analysis of a Local Search Heuristic for Facility Location Problems. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1--10. Society for Industrial and Applied Mathematics, 1998.

Digital Library

[15]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. Initializing newly deployed ad hoc and sensor networks. In Proceedings of 10th Annual International Conference on Mobile Computing and Networking (MOBICOM), pages 260--274, 2004.

Digital Library

[16]

F. Kuhn, T. Moscibroda, and R. Wattenhofer. What Cannot be Computed Locally! In Proceedings of the 23rd ACM Symposium on the Principles of Distributed Computing (PODC), pages 300--309, 2004.

Digital Library

[17]

F. Kuhn and R. Wattenhofer. Constant-Time Distributed Dominating Set Approximation. In Proc. of the 22nd Annual ACM Symp. on Principles of Distributed Computing (PODC), pages 25--32, 2003.

Digital Library

[18]

J.-H. Lin and J. S. Vitter. ε-Approximations with Minimum Packing Constraint Violation. In Proceedings of the 24th ACM Symposium on Theory of Computing (STOC), pages 771--782, 1992.

Digital Library

[19]

N. Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1):193--201, 1992.

Digital Library

[20]

Z. Lotker, E. Pavlov, B. Patt-Shamir, and D. Peleg. MST Construction in O(log log n) Communication Rounds. In Proceedings of the 15th ACM symposium on Parallel Algorithms and Architectures (SPAA), pages 94--100. ACM Press, 2003.

Digital Library

[21]

M. Luby and N. Nisan. A Parallel Approximation Algorithm for Positive Linear Programming. In Proc. of the 25th ACM Symposium on Theory of Computing (STOC), pages 448--457, 1993.

Digital Library

[22]

C. Lund and M. Yannakakis. On the Hardness of Approximating Minimization Problems. Journal of the ACM, 41(5).

Digital Library

[23]

C. Papadimitriou and M. Yannakakis. Linear Programming Without the Matrix. In Proceedings of the 25th ACM Symposium on Theory of Computing (STOC), pages 121--129. ACM Press, 1993.

Digital Library

[24]

D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Mathematics and Applications, 2000.

Digital Library

[25]

D. Peleg and V. Rubinovich. A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction. SIAM J. Comput., 30(5):1427--1442, 2001.

Digital Library

[26]

S. Rajagopalan and V. Vazirani. Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs. SIAM Journal on Computing, 28:525--540, 1998.

Digital Library

[27]

D. B. Shmoys, E. Tardos, and K. I. Aardal. Approximation Algorithms for Facility Location Problems. In Proc. 29th Symposium on Theory of Computing (STOC), pages 265--274, 1997.

Digital Library

[28]

C. Swamy and D. B. Shmoys. Fault-Tolerant Facility Location. In Proc. 14th Symposium on Discrete Algorithms (SODA), pages 735--736, 2003.

Digital Library

[29]

D. P. Williamson, M. X. Goemans, M. Mihail, and V. V. Vazirani. A Primal-Dual Approximation Algorithm for Generalized Steiner Network Problems. In Proc. 25th Symposium on Theory of Computing (STOC), pages 708--717, 1993.

Digital Library

Cited By

Parsaeefard SRoessel SGholami Ghavamabad AZaus RRaaf B(2024)Leader Selection and Follower Association for UE-Centric Distributed Learning in Future Wireless NetworksIEEE Access10.1109/ACCESS.2024.348226012(154160-154172)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3482260
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
Hanada KAmemiya YSugimoto K(2022)A Distributed Asynchronous Heuristic Algorithm in Generalized Mutual Assignment ProblemTransactions of the Japanese Society for Artificial Intelligence10.1527/tjsai.37-2_B-L8137:2(B-L81_1-11)Online publication date: 1-Mar-2022
https://doi.org/10.1527/tjsai.37-2_B-L81
Show More Cited By

Index Terms

Facility location: distributed approximation
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Network flows
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows
  2. Randomness, geometry and discrete structures

Recommendations

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

In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our ...
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 ...
Kinetic Facility Location

We present a deterministic kinetic data structure for the facility location problem that maintains a subset of the moving points as facilities such that, at any point of time, the accumulated cost for the whole point set is at most a constant factor ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '05: Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing

July 2005

364 pages

ISBN:1581139942

DOI:10.1145/1073814

General Chair:
Marcos Aguilera
HP Labs
,
Program Chair:
James Aspnes
Yale University

Copyright © 2005 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: 17 July 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC05

Sponsor:

PODC05: ACM Symposium on Principles of Distributed Computing

July 17 - 20, 2005

NV, Las Vegas, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
577
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Parsaeefard SRoessel SGholami Ghavamabad AZaus RRaaf B(2024)Leader Selection and Follower Association for UE-Centric Distributed Learning in Future Wireless NetworksIEEE Access10.1109/ACCESS.2024.348226012(154160-154172)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3482260
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
Hanada KAmemiya YSugimoto K(2022)A Distributed Asynchronous Heuristic Algorithm in Generalized Mutual Assignment ProblemTransactions of the Japanese Society for Artificial Intelligence10.1527/tjsai.37-2_B-L8137:2(B-L81_1-11)Online publication date: 1-Mar-2022
https://doi.org/10.1527/tjsai.37-2_B-L81
Tsipis AKomianos VOikonomou KStavrakakis I(2020)Elastic Distributed Rendering Service Placement in Capacitated Cloud/Fog Gaming Systems2020 11th International Conference on Information, Intelligence, Systems and Applications (IISA10.1109/IISA50023.2020.9284390(1-8)Online publication date: 15-Jul-2020
https://doi.org/10.1109/IISA50023.2020.9284390
Aral AOvatman T(2018)A Decentralized Replica Placement Algorithm for Edge ComputingIEEE Transactions on Network and Service Management10.1109/TNSM.2017.278894515:2(516-529)Online publication date: Jun-2018
https://doi.org/10.1109/TNSM.2017.2788945
Krishnan AMarkov MBonakdarpour B(2017)Distributed Vehicle Routing Approximation2017 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2017.90(503-512)Online publication date: May-2017
https://doi.org/10.1109/IPDPS.2017.90
Zhao YJiang HZhou KHuang ZHuang P(2016)DREAM-(L)GIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2016.253733427:12(3469-3484)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1109/TPDS.2016.2537334
Chen FLin HGao YLu D(2016)Capacity constrained maximizing bichromatic reverse nearest neighbor searchExpert Systems with Applications: An International Journal10.1016/j.eswa.2015.08.05143:C(93-108)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.eswa.2015.08.051
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

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.

Figures

Tables

Media

View Table of Conten