Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10515280" target="_blank" >RIV/00216208:11320/25:10515280 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=n~_8kV90Oh" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=n~_8kV90Oh</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3742476" target="_blank" >10.1145/3742476</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond

Popis výsledku v původním jazyce

We develop a general deterministic distributed method for locally rounding fractional solutions of graph problems for which the analysis can be broken down into analyzing pairs of vertices. Roughly speaking, the method can transform fractional/probabilistic label assignments of the vertices into integral/deterministic label assignments for the vertices, while approximately preserving a potential function that is a linear combination of functions, each of which depends on at most two vertices (subject to some conditions usually satisfied in pairwise analyses). The method unifies and significantly generalizes prior work on deterministic local rounding obtain polylogarithmic-time deterministic distributed solutions for combinatorial graph problems. Our general rounding result enables us to locally and efficiently derandomize a range of distributed algorithms for local and minimum-cost set cover approximation. As highlights, we, in particular, obtain the following results. -We obtain a deterministic O (log(2) Delta &lt;middle dot&gt; log n)-round algorithm for computing an MIS in the LOCAL model and an almost as efficient O (log(2) Delta &lt;middle dot&gt; log log Delta &lt;middle dot&gt; log n)-round deterministic MIS algorithm in the CONGEST model. As a result, the best known deterministic distributed time complexity of the four most widely studied distributed symmetry breaking problems (MIS, maximal matching, (Delta + 1)-vertex coloring, and (2 Delta - 1)-edge coloring) is now O (log(2) Delta &lt;middle dot&gt; log n). Our new MIS algorithm is also the first direct polylogarithmic-time deterministic distributed MIS algorithm, which is not based on network decomposition. -We obtain efficient deterministic distributed algorithms for rounding fractional solutions for maximum (weighted) independent set and minimum (weighted) set cover. In particular, for any constant epsilon &gt; 0, we give a deterministic O (log(2) A + log* n)-round algorithm for computing an independent set of size (1/2 -epsilon) &lt;middle dot&gt; n/deg(avg), and we give deterministic O(log(2)(Delta W) + log* n)-round algorithms for computing a (1 - epsilon)/Delta-approximation of maximum weight independent set, and for computing a (1 - epsilon)/r-approximation of maximum weight matching in hypergraphs of rank r. For minimum set cover instances with sets of size at most sand where each element is contained in at most t sets, we show that an O (log s)-approximation can be computed in time O (log s &lt;middle dot&gt; log(2) t + log(&amp; lowast; )n).

Název v anglickém jazyce

Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond

Popis výsledku anglicky

We develop a general deterministic distributed method for locally rounding fractional solutions of graph problems for which the analysis can be broken down into analyzing pairs of vertices. Roughly speaking, the method can transform fractional/probabilistic label assignments of the vertices into integral/deterministic label assignments for the vertices, while approximately preserving a potential function that is a linear combination of functions, each of which depends on at most two vertices (subject to some conditions usually satisfied in pairwise analyses). The method unifies and significantly generalizes prior work on deterministic local rounding obtain polylogarithmic-time deterministic distributed solutions for combinatorial graph problems. Our general rounding result enables us to locally and efficiently derandomize a range of distributed algorithms for local and minimum-cost set cover approximation. As highlights, we, in particular, obtain the following results. -We obtain a deterministic O (log(2) Delta &lt;middle dot&gt; log n)-round algorithm for computing an MIS in the LOCAL model and an almost as efficient O (log(2) Delta &lt;middle dot&gt; log log Delta &lt;middle dot&gt; log n)-round deterministic MIS algorithm in the CONGEST model. As a result, the best known deterministic distributed time complexity of the four most widely studied distributed symmetry breaking problems (MIS, maximal matching, (Delta + 1)-vertex coloring, and (2 Delta - 1)-edge coloring) is now O (log(2) Delta &lt;middle dot&gt; log n). Our new MIS algorithm is also the first direct polylogarithmic-time deterministic distributed MIS algorithm, which is not based on network decomposition. -We obtain efficient deterministic distributed algorithms for rounding fractional solutions for maximum (weighted) independent set and minimum (weighted) set cover. In particular, for any constant epsilon &gt; 0, we give a deterministic O (log(2) A + log* n)-round algorithm for computing an independent set of size (1/2 -epsilon) &lt;middle dot&gt; n/deg(avg), and we give deterministic O(log(2)(Delta W) + log* n)-round algorithms for computing a (1 - epsilon)/Delta-approximation of maximum weight independent set, and for computing a (1 - epsilon)/r-approximation of maximum weight matching in hypergraphs of rank r. For minimum set cover instances with sets of size at most sand where each element is contained in at most t sets, we show that an O (log s)-approximation can be computed in time O (log s &lt;middle dot&gt; log(2) t + log(&amp; lowast; )n).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

ACM Transactions on Algorithms

ISSN

1549-6325

e-ISSN

1549-6333

Svazek periodika

21

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

48

Strana od-do

42

Kód UT WoS článku

001576309200012

EID výsledku v databázi Scopus

2-s2.0-105018673577