Inamdar, Tanmay ;
Pai, Shreyas ;
Pemmaraju, Sriram V.
LargeScale Distributed Algorithms for Facility Location with Outliers
Abstract
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 kmachine 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 edgeweighted 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 kmachine 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 kmachine model.
Our main contribution is to show the existence of MettuPlaxtonstyle 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) MettuPlaxton style algorithms are more easily amenable to being implemented efficiently in distributed and largescale models of computation.
BibTeX  Entry
@InProceedings{inamdar_et_al:LIPIcs:2018:10065,
author = {Tanmay Inamdar and Shreyas Pai and Sriram V. Pemmaraju},
title = {{LargeScale Distributed Algorithms for Facility Location with Outliers}},
booktitle = {22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
pages = {5:15:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770989},
ISSN = {18688969},
year = {2018},
volume = {125},
editor = {Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10065},
URN = {urn:nbn:de:0030drops100650},
doi = {10.4230/LIPIcs.OPODIS.2018.5},
annote = {Keywords: Distributed Algorithms, Clustering with Outliers, Metric Facility Location, Massively Parallel Computation, kmachine model, Congested Clique}
}
15.01.2019
Keywords: 

Distributed Algorithms, Clustering with Outliers, Metric Facility Location, Massively Parallel Computation, kmachine model, Congested Clique 
Seminar: 

22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Issue date: 

2018 
Date of publication: 

15.01.2019 