An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
Author:
- Michael ElkinMEMichael Elkin
- 1 January 2006
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 36 (2) , 433-456
Abstract
The design of distributed approximation protocols is a relatively new and rapidly developing area of research. However, so far, little progress has been made in the study of the hardness of distributed approximation. In this paper we initiate the systematic study of this subject and show strong unconditional lower bounds on the time-approximation trade-off of the distributed minimum spanning tree problem, and show some of its variants.Keywords
This publication has 17 references indexed in Scilit:
- Global optimization models in data networks: a case studyComputers & Operations Research, 2006
- Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletonsJournal of Computer and System Sciences, 2005
- Computing almost shortest pathsACM Transactions on Algorithms, 2005
- Distributed approximationACM SIGACT News, 2004
- Distributed algorithm for approximating the maximum matchingDiscrete Applied Mathematics, 2004
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning TreesSIAM Journal on Computing, 1998
- Nearly optimal distributed edge coloring in O(log log n) roundsRandom Structures & Algorithms, 1997
- Approximating matchings in parallelInformation Processing Letters, 1993
- A new distributed algorithm to find breadth first search treesIEEE Transactions on Information Theory, 1987
- A Distributed Algorithm for Minimum-Weight Spanning TreesACM Transactions on Programming Languages and Systems, 1983