License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2018.5
URN: urn:nbn:de:0030-drops-100650
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10065/
Go to the corresponding LIPIcs Volume Portal

Inamdar, Tanmay ; Pai, Shreyas ; Pemmaraju, Sriram V.

Large-Scale Distributed Algorithms for Facility Location with Outliers

pdf-format:
LIPIcs-OPODIS-2018-5.pdf (0.5 MB)

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 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.

BibTeX - Entry

@InProceedings{inamdar_et_al:LIPIcs:2018:10065,
  author =	{Tanmay Inamdar and Shreyas Pai and Sriram V. Pemmaraju},
  title =	{{Large-Scale Distributed Algorithms for Facility Location with Outliers}},
  booktitle =	{22nd International Conference on Principles of Distributed  Systems (OPODIS 2018)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{125},
  editor =	{Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10065},
  URN =		{urn:nbn:de:0030-drops-100650},
  doi =		{10.4230/LIPIcs.OPODIS.2018.5},
  annote =	{Keywords: Distributed Algorithms, Clustering with Outliers, Metric Facility Location, Massively Parallel Computation, k-machine model, Congested Clique}
}

Keywords: Distributed Algorithms, Clustering with Outliers, Metric Facility Location, Massively Parallel Computation, k-machine model, Congested Clique
Collection: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)
Issue Date: 2018
Date of publication: 15.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI