期刊
JOURNAL OF THE ACM
卷 60, 期 5, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2528405
关键词
Algorithms; Theory; Approximation algorithms; deterministic distributed algorithms; edge dominating set; local algorithms; unique identifiers
类别
资金
- Academy of Finland [132380, 252018]
- Research Funds of the University of Helsinki
- Finnish Cultural Foundation
- Academy of Finland (AKA) [252018, 132380, 252018, 132380] Funding Source: Academy of Finland (AKA)
In the study of deterministic distributed algorithms, it is commonly assumed that each node has a unique O(log n)-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributed algorithms) do not need such identifiers: a port numbering and orientation is sufficient. Our result holds for so-called simple PO-checkable graph optimisation problems; this includes many classical packing and covering problems such as vertex covers, edge covers, matchings, independent sets, dominating sets, and edge dominating sets. We focus on the case of bounded-degree graphs and show that if a local algorithm finds a constant-factor approximation of a simple PO-checkable graph problem with the help of unique identifiers, then the same approximation ratio can be achieved on anonymous networks. As a corollary of our result, we derive a tight lower bound on the local approximability of the minimum edge dominating set problem. By prior work, there is a deterministic local algorithm that achieves the approximation factor of 4 -1/left perpendicular Delta/2right perpendicular in graphs of maximum degree Delta. This approximation ratio is known to be optimal in the port-numbering model-our main theorem implies that it is optimal also in the standard model in which each node has a unique identifier. Our main technical tool is an algebraic construction of homogeneously ordered graphs: We say that a graph is (alpha, r)-homogeneous if its nodes are linearly ordered so that an alpha fraction of nodes have pairwise isomorphic radius-r neighbourhoods. We show that there exists a finite (alpha, r)-homogeneous 2k-regular graph of girth at least g for any alpha < 1 and any r, k, and g.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据