Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
Michael Elkin · 2004
The design of distributed approximation protocols is a relatively new rapidly developing area of research. However, so far little progress was done 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 tradeoff of the distributed minimum spanning tree problem, and some of its variants.