What Can Be Approximated Locally?

ABSTRACT Whether local algorithms can compute,constant approximations,of NP-hard problems,is of both practical and theoretical interest. So far, no algorithms achieving this goal are known, as either the ap- proximation ratio or the running time exceed O(1), or the nodes are provided with non-trivial additional information. In this pa- per, we present the first distributed algorithm approximating a min- imum,dominating,set on a planar graph within a constant factor in constant time. Moreover, the nodes do not need any additional information. Categories and Subject Descriptors