  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.

Distributed, Parallel, and Cluster Computing;Data Structures and Algorithms