10.4230/LIPICS.OPODIS.2018.5
Inamdar, Tanmay
Tanmay
Inamdar
Department of Computer Science, The University of Iowa, Iowa, USA
Pai, Shreyas
Shreyas
Pai
Department of Computer Science, The University of Iowa, Iowa, USA
Pemmaraju, Sriram V.
Sriram V.
Pemmaraju
Department of Computer Science, The University of Iowa, Iowa, USA
Large-Scale Distributed Algorithms for Facility Location with Outliers
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2019
Distributed Algorithms
Clustering with Outliers
Metric Facility Location
Massively Parallel Computation
k-machine model
Congested Clique
Cao, Jiannong
Jiannong
Cao
Ellen, Faith
Faith
Ellen
Rodrigues, Luis
Luis
Rodrigues
Ferreira, Bernardo
Bernardo
Ferreira
2019
2019-01-15
2019-01-15
2019-01-15
en
urn:nbn:de:0030-drops-100650
arXiv:1811.06494
10.4230/LIPIcs.OPODIS.2018
978-3-95977-098-9
1868-8969
10.1145/237814.237823
10.1145/2591796.2591805
10.1007/978-3-540-39658-1_6
10.1145/3154273.3154317
10.1145/2463664.2465224
10.4230/LIPIcs.DISC.2017.7
arXiv:1802.10297
10.1007/978-3-642-31585-5_39
10.1145/2767386.2767414
10.1145/1629175.1629198
10.1145/2020408.2020515
10.1145/2806416.2806508
10.1145/1148109.1148152
10.1145/3087801.3087830
10.1145/3212734.3212743
10.1007/978-3-642-25591-5_39
10.1016/j.tcs.2015.09.029
10.1007/s00446-015-0243-x
arXiv:1408.2071
arXiv:1811.06494
10.1145/375827.375845
10.1145/2484239.2501983
10.1145/1807167.1807184
10.1137/S0097539701383443
10.1145/2935764.2935785
10.1145/3210377.3210409
10.1145/1993806.1993851
10.1145/2522968.2522981
10.1137/S0097539701388884
10.4230/LIPIcs.OPODIS.2018
LIPIcs, Volume 125, OPODIS 2018
22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
2019
125
5
5:1
5:16
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Cao, Jiannong
Jiannong
Cao
Ellen, Faith
Faith
Ellen
Rodrigues, Luis
Luis
Rodrigues
Ferreira, Bernardo
Bernardo
Ferreira
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2019
125
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
16 pages
516917 bytes
application/pdf
1.0
Creative Commons Attribution 3.0 Unported license
info:eu-repo/semantics/openAccess
This paper presents fast, distributed, O(1)-approximation algorithms for metric facility location problems with outliers in the Congested Clique model, Massively Parallel Computation (MPC) model, and in the k-machine model. The paper considers Robust Facility Location and Facility Location with Penalties, two versions of the facility location problem with outliers proposed by Charikar et al. (SODA 2001). The paper also considers two alternatives for specifying the input: the input metric can be provided explicitly (as an n x n matrix distributed among the machines) or implicitly as the shortest path metric of a given edge-weighted graph. The results in the paper are:
- Implicit metric: For both problems, O(1)-approximation algorithms running in O(poly(log n)) rounds in the Congested Clique and the MPC model and O(1)-approximation algorithms running in O~(n/k) rounds in the k-machine model.
- Explicit metric: For both problems, O(1)-approximation algorithms running in O(log log log n) rounds in the Congested Clique and the MPC model and O(1)-approximation algorithms running in O~(n/k) rounds in the k-machine model.
Our main contribution is to show the existence of Mettu-Plaxton-style O(1)-approximation algorithms for both Facility Location with outlier problems. As shown in our previous work (Berns et al., ICALP 2012, Bandyapadhyay et al., ICDCN 2018) Mettu-Plaxton style algorithms are more easily amenable to being implemented efficiently in distributed and large-scale models of computation.
LIPIcs, Vol. 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018), pages 5:1-5:16