Book chapter
Super-Fast Distributed Algorithms for Metric Facility Location
Automata, Languages, and Programming, pp.428-439
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2012
DOI: 10.1007/978-3-642-31585-5_39
Abstract
This paper presents a distributed O(1)-approximation algorithm in the \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal{CONGEST}$\end{document} model for the metric facility location problem on a size-n clique network that has an expected running time of O(loglogn ·log*n) rounds. 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. Since the facility location problem is specified by Ω(n2) bits of information, any fast solution in the \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$\mathcal{CONGEST}$\end{document} model must be truly distributed. Our paper makes three main technical contributions. First, we show a new lower bound for metric facility location. 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.
Details
- Title: Subtitle
- Super-Fast Distributed Algorithms for Metric Facility Location
- Creators
- Andrew Berns - University of IowaJames Hegeman - University of IowaSriram V. Pemmaraju - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Automata, Languages, and Programming, pp.428-439
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-642-31585-5_39
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2012
- Academic Unit
- Computer Science
- Record Identifier
- 9984259485302771
Metrics
7 Record Views