NDLI: Lower bounds for local approximation

Content Provider	ACM Digital Library
Author	Gs, Mika Hirvonen, Juho Suomela, Jukka
Copyright Year	2013
Abstract	In the study of deterministic distributed algorithms, it is commonly assumed that each node has a unique $\textit{O}(log$ $\textit{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 $\textit{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/⌊Δ/2⌋ in graphs of maximum degree Δ. 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 $(α,\textit{r})-homogeneous$ if its nodes are linearly ordered so that an α fraction of nodes have pairwise isomorphic $radius-\textit{r}$ neighbourhoods. We show that there exists a finite $(α,\textit{r})-homogeneous$ $2\textit{k}-regular$ graph of girth at least $\textit{g}$ for any α < 1 and any $\textit{r},$ $\textit{k},$ and $\textit{g}.$
Starting Page	1
Ending Page	23
Page Count	23
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2528405
Journal	Journal of the ACM (JACM)
Volume Number	60
Issue Number	5
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-10-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximation algorithms Deterministic distributed algorithms Edge dominating set Local algorithms Unique identifiers
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Lower bounds for local approximation

Local Computation: Lower and Upper Bounds

Lower Bounds for Distributed Maximum-Finding Algorithms

Lower Bounds on Information Transfer in Distributed Computations

Lower Bounds and Fast Algorithms for Sequence Acceleration

Lower bounds on communication complexity in distributed computer networks

Tight bounds for asynchronous randomized consensus

Lower Bounds on Merging Networks

Tight Bounds for Asynchronous Renaming

Lower bounds for local approximation

Similar Documents

Lower bounds for local approximation

Local Computation: Lower and Upper Bounds

Lower Bounds for Distributed Maximum-Finding Algorithms

Lower Bounds on Information Transfer in Distributed Computations

Lower Bounds and Fast Algorithms for Sequence Acceleration

Lower bounds on communication complexity in distributed computer networks

Tight bounds for asynchronous randomized consensus

Lower Bounds on Merging Networks

Tight Bounds for Asynchronous Renaming

Lower bounds for local approximation