arXiv preprint ·
Almost Lossless Transfer for Cuttable Distributed Problems
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Federated Coreset Subsampling for Distributed Memory Banks
A Quantum Analogue of the Covering Lemma: Limits of Exact Anonymous Computation
Distributed $(Δ+1)$-Coloring in $O(\sqrtΔ+\log^* n)$ Rounds
DualColl: Throughput-Optimal Bandwidth-Bound Collective Communications via Fractional Tree Packing
Prorsa: Unleashing the Potential of Prefill-Decode Disaggregation in Agentic Reinforcement Learning
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.