Journal article
Sub-logarithmic distributed algorithms for metric facility location
Distributed computing, Vol.28(5), pp.351-374
10/01/2015
DOI: 10.1007/s00446-015-0243-x
Abstract
The facility location problem consists of a set of facilities , a set of clients , an opening cost associated with each facility , and a connection cost between each facility and client . The goal is to find a subset of facilities to open, and to connect each client to an open facility, so as to minimize the total facility opening costs plus connection costs. We consider distributed versions of facility location in which the underlying network is either a clique, in which each node is both a client and a facility (and ), or a complete bipartite network, with forming the bipartition. This paper presents the first expected-sub-logarithmic-round distributed -approximation algorithms in the model for the metric facility location problem. We present our approach first for a clique network, and then extend it to a bipartite network. Our algorithms have expected running times of rounds, where , and where for a clique network and for a bipartite network (These results were first published in ICALP 2012 and DISC 2013). In order to obtain these results, our paper makes four main technical contributions. First, we show a new lower bound for metric facility location, extending the lower bound of Bdoiu 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 -ruling set of an appropriate spanning subgraph. Third, we provide an expected-sub-logarithmic-round algorithm for computing a -ruling set in a spanning subgraph of a clique. Finally, we present a new technique based on probabilistic hashing to solve a problem of information dissemination on bipartite networks.
Details
- Title: Subtitle
- Sub-logarithmic distributed algorithms for metric facility location
- Creators
- James W. Hegeman - University of IowaSriram V. Pemmaraju - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Distributed computing, Vol.28(5), pp.351-374
- Publisher
- Springer Nature
- DOI
- 10.1007/s00446-015-0243-x
- ISSN
- 0178-2770
- eISSN
- 1432-0452
- Number of pages
- 24
- Grant note
- 1318166 / Direct For Computer & Info Scie & Enginr; National Science Foundation (NSF); NSF - Directorate for Computer & Information Science & Engineering (CISE) CCF 0915543; CCF 1318166 / National Science Foundation; National Science Foundation (NSF)
- Language
- English
- Date published
- 10/01/2015
- Academic Unit
- Computer Science
- Record Identifier
- 9984259499102771
Metrics
2 Record Views