### Local Computation: Lower and Upper BoundsLocal Computation: Lower and Upper Bounds

Access Restriction
Subscribed

 Author Kuhn, Fabian ♦ Moscibroda, Thomas ♦ Wattenhofer, Roger Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2016 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Approximation hardness ♦ Butterfly effect ♦ Distributed algorithms ♦ Dominating set ♦ Locality ♦ Lower bounds ♦ Maximal independent set ♦ Maximal matching ♦ Polylog-local ♦ Vertex cover Abstract The question of what can be computed, and how efficiently, is at the core of computer science. Not surprisingly, in distributed systems and networking research, an equally fundamental question is what can be computed in a $\textit{distributed}$ fashion. More precisely, if nodes of a network must base their decision on information in their local neighborhood only, how well can they compute or approximate a global (optimization) problem? In this paper we give the first polylogarithmic lower bound on such local computation for (optimization) problems including minimum vertex cover, minimum (connected) dominating set, maximum matching, maximal independent set, and maximal matching. In addition, we present a new distributed algorithm for solving general covering and packing linear programs. For some problems this algorithm is tight with the lower bounds, whereas for others it is a distributed approximation scheme. Together, our lower and upper bounds establish the local computability and approximability of a large class of problems, characterizing how much local information is required to solve these tasks. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2016-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 63 Issue Number 2 Page Count 44 Starting Page 1 Ending Page 44

#### Open content in new tab

Source: ACM Digital Library