Large-Scale Distributed Algorithms for Facility Location with Outliers
Large-Scale Distributed Algorithms for Facility Location with Outliers
复制标题
具有异常值的设施定位的大规模分布式算法
DOI：
10.4230/lipics.opodis.2018.5
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Sriram V. Pemmaraju
中科院分区：
文献类型：
--
作者：
Tanmay Inamdar;Shreyas Pai;Sriram V. Pemmaraju
本文提出了快速，分布式，O（1）$近似算法的度量设施选址问题的离群点在拥挤集团模型，大规模并行计算（MPC）模型，和在$k$-机模型。本文考虑了Charikar等人（SODA 2001）提出的带离群值的设施选址问题的两个版本：鲁棒设施选址和带惩罚的设施选址。本文还考虑了两种替代指定的输入：输入度量可以显式地提供（作为一个$n \times n$矩阵分布在机器之间）或隐式地作为一个给定的边加权图的最短路径度量。本文的结果是：
- 隐式度量：对于这两个问题，$O（1）$-近似算法在拥挤集团和MPC模型中运行$O（\mbox{poly}（\log n））$轮，$O（1）$-近似算法在$k$-机器模型中运行$\tilde{O}（n/k）$轮。
- 显式度量：对于这两个问题，在拥挤集团和MPC模型中运行$O（\log\log\log n）$轮的$O（1）$-近似算法和在$k$-机器模型中运行$O（O）（n/k）$轮的$O（1）$-近似算法。
我们的主要贡献是显示存在的Mettu-Plaxton风格的$O（1）$-近似算法的设施选址与离群值问题。如我们以前的工作所示（Berns等人，ICALP 2012，Bandyapadhyay等人，ICDCN 2018）Mettu-Plaxton风格的算法更容易在分布式和大规模计算模型中有效实现。
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 \times 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(\mbox{poly}(\log n))$ rounds in the Congested Clique and the MPC model and $O(1)$-approximation algorithms running in $\tilde{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 $\tilde{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.
DOI：
10.1145/3210377.3210409
发表时间：
2016-02
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
通讯作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato