Super-fast distributed algorithms for metric facility location

DOI10.1007/978-3-642-31585-5_39MaRDI QIDQ3167031zbMATH OpenOpenAlexFDO

Authors Andrew Berns, James W. Hegeman, Sriram Pemmaraju

Publication date 1 November 2012

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.2473

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Distributed algorithms (68W15) Discrete location and assignment (90B80)

Abstract: This paper presents a distributed O(1)-approximation algorithm, with expected-$O(loglogn)$ running time, in the $mathcalCONGEST$ model for the metric facility location problem on a size-$n$ clique network. Though metric facility location has been considered by a number of researchers in low-diameter settings, this is the first sub-logarithmic-round algorithm for the problem that yields an O(1)-approximation in the setting of non-uniform facility opening costs. In order to obtain this result, our paper makes three main technical contributions. First, we show a new lower bound for metric facility location, extending the lower bound of Bu{a}doiu et al. (ICALP 2005) that applies only to the special case of uniform facility opening costs. Next, we demonstrate a reduction of the distributed metric facility location problem to the problem of computing an O(1)-ruling set of an appropriate spanning subgraph. Finally, we present a sub-logarithmic-round (in expectation) algorithm for computing a 2-ruling set in a spanning subgraph of a clique. Our algorithm accomplishes this by using a combination of randomized and deterministic sparsification.

Recommendations

• Sub-logarithmic distributed algorithms for metric facility location
• Return of the primal-dual, distributed metric facility location
• A distributed O(1)-approximation algorithm for the uniform facility location problem
• A distributed approximation algorithm for fault-tolerant metric facility location
• Facility location, distributed approximation

Cited in

(9)

• Return of the primal-dual, distributed metric facility location
• Large-scale distributed algorithms for facility location with outliers
• Sub-logarithmic distributed algorithms for metric facility location
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• Lessons from the congested clique applied to MapReduce
• Rapid randomized pruning for fast greedy distributed algorithms
• \((\Delta+1)\) coloring in the congested clique model
• Facility location, distributed approximation
• A distributed O(1)-approximation algorithm for the uniform facility location problem

This page was built for publication: Super-fast distributed algorithms for metric facility location

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167031)