An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
Michael Elkin · SIAM Journal on Computing · 2006
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.