Local Computation: Lower and Upper Bounds

Details Local Computation: Lower and Upper Bounds Local Computation: Lower and Upper Bounds

2010-11-24

arxiv.org/abs/1011.5470v1

Computer Science

Distributed, Parallel, and Cluster Computing

53 pages, preliminary version in ACM PODC 2004 and ACM-SIAM SODA 2006

Scientific paper

The question of what can be computed, and how efficiently, are 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 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 substantial 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, 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.

Affiliated with

Also associated with

No associations

Rating

Local Computation: Lower and Upper Bounds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Local Computation: Lower and Upper Bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Local Computation: Lower and Upper Bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-241693