Conference proceeding
Rapid randomized pruning for fast greedy distributed algorithms
Proceedings of the 29th ACM SIGACT-SIGOPS symposium on principles of distributed computing, pp.325-334
PODC '10
07/25/2010
DOI: 10.1145/1835698.1835777
Abstract
We start by defining a pruning process involving sellers on one side and buyers on the other. The goal is to quickly select a subset of the sellers so that the products that these sellers bring to the market has small cost ratio , i.e., the ratio of the total cost of the selected sellers' products to amount that interested buyers are willing to pay. As modeled here, the pruning process can be used to speed up distributed implementations of greedy algorithms (e.g., for minimum dominating set, facility location, etc). We present a randomized instance of the pruning process that, for any positive k , runs in O(k) communication rounds with O (log N )-sized messages, yielding a cost ratio of O(N c/k ) . Here N is the product of the number of sellers and number of buyers and c is a small constant. Using this O(k) -round pruning algorithm as the basis, we derive several simple, greedy, O(k) -round distributed approximation algorithms for MDS and facility location (both metric and non-metric versions). Our algorithms achieve optimal approximation ratios in polylogarithmic rounds and shave a "logarithmic factor" off the best, known, approximation factor, typically achieved using LP-rounding techniques.
Details
- Title: Subtitle
- Rapid randomized pruning for fast greedy distributed algorithms
- Creators
- Saurav Pandit - University of IowaSriram Pemmaraju - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the 29th ACM SIGACT-SIGOPS symposium on principles of distributed computing, pp.325-334
- Series
- PODC '10
- DOI
- 10.1145/1835698.1835777
- Publisher
- ACM
- Language
- English
- Date published
- 07/25/2010
- Academic Unit
- Computer Science
- Record Identifier
- 9984259435502771
Metrics
6 Record Views