Book chapter
Finding Facilities Fast
Distributed Computing and Networking, pp.11-24
Lecture Notes in Computer Science, Springer Berlin Heidelberg
2009
DOI: 10.1007/978-3-540-92295-7_5
Abstract
Clustering can play a critical role in increasing the performance and lifetime of wireless networks. The facility location problem is a general abstraction of the clustering problem and this paper presents the first constant-factor approximation algorithm for the facility location problem on unit disk graphs (UDGs), a commonly used model for wireless networks. In this version of the problem, connection costs are not metric, i.e., they do not satisfy the triangle inequality, because connecting to a non-neighbor costs ∞. In non-metric settings the best approximation algorithms guarantee an O(logn)-factor approximation, but we are able to use structural properties of UDGs to obtain a constant-factor approximation. Our approach combines ideas from the primal-dual algorithm for facility location due to Jain and Vazirani (JACM, 2001) with recent results on the weighted minimum dominating set problem for UDGs (Huang et al., J. Comb. Opt., 2008). We then show that the facility location problem on UDGs is inherently local and one can solve local subproblems independently and combine the solutions in a simple way to obtain a good solution to the overall problem. This leads to a distributed version of our 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{LOCAL}$\end{document} model that runs in constant rounds and still yields a constant-factor approximation. Even if the UDG is specified without geometry, we are able to combine recent results on maximal independent sets and clique partitioning of UDGs, to obtain an O(logn)-approximation that runs in O(log*n) rounds.
Details
- Title: Subtitle
- Finding Facilities Fast
- Creators
- Saurav Pandit - University of IowaSriram V. Pemmaraju - University of Iowa
- Resource Type
- Book chapter
- Publication Details
- Distributed Computing and Networking, pp.11-24
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/978-3-540-92295-7_5
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 2009
- Academic Unit
- Computer Science
- Record Identifier
- 9984259405202771
Metrics
9 Record Views