Improved algorithms for local approximation in network graph problems
Almost Lossless Transfer for Cuttable Distributed Problems
Data Structures and AlgorithmsDistributed, Parallel, and Cluster Computing
Summary
The paper studies how to find near-optimal small sets of points in networks using only local information, with very limited rounds of communication. The authors improve previous methods by reducing extra costs in approximations for certain complex network classes. Their new algorithms carefully detect and fix errors better and use clever averaging techniques to get closer to the best solutions. They show that these methods offer stronger guarantees for network graphs, including some that were not covered before.
What this means in practice
- •For network designers: Produce efficient near-optimal solutions for local control tasks on networks with complex structures using distributed algorithms with fewer communication steps.
- •For distributed systems engineers: Improve algorithms for minimizing resource usage in distributed systems by applying better local approximations on graphs formed by combining simple and complex components.
Authors
Wojciech Wawrzyniak
Abstract
We study constant-round LOCAL approximation for additive local vertex-subset minimization problems. Given a $k$-uniform $α$-approximation on a hereditary source class closed under disjoint union, Bonamy, Das, Gavoille, Picavet, Suomela, and Wesolek obtained ratio $α(d+1)+1$ on locally nice target classes of asymptotic dimension $d$. We prove two transfers with ratios $α+1+η$ and $α+η$ for every $η>0$. These bounds require the stronger local niceness assumption at a larger scale that depends on $η$. The first algorithm keeps their repair construction and increases the radius used to detect errors. We average over partitions of the graph to bound the retained cost without the factor $d+1$. These partitions are used only in the analysis. The second algorithm tests several deletion widths around the errors. In each component of the repair zone, it chooses a smallest union of retained choices and an exact repair. Averaging over the widths bounds the cost counted twice and yields ratio $α+η$. Both transfers are deterministic and computable, use arbitrary distinct numerical identifiers, and need no knowledge of the graph size. Their outputs also satisfy local uniformity guarantees. For 2-domination on graphs of bounded Euler genus, the same planar source gives ratio $19$ through the earlier transfer and $6+η$ through ours. For minimum dominating set, our transfer gives ratio $7+\varepsilon$ on graphs formed by attaching a clique of arbitrary size at one vertex of a planar graph, using the source algorithm of Amiri and Siebertz. This class satisfies our target assumptions and allows nonempty error sets. Its Euler genus is unbounded, so their guarantee for graphs of bounded Euler genus does not cover the whole class.