Open access
Datum
2023Typ
- Journal Article
ETH Bibliographie
yes
Altmetrics
Abstract
We describe a simple deterministic O(e-1 log A) round distributed algorithm for (2a + 1)(1 + e) approximation of minimum weighted dominating set on graphs with arboricity at most a. Here A denotes the maximum degree. We also show a lower bound proving that this round complexity is nearly optimal even for the unweighted case, via a reduction from the celebrated KMW lower bound on distributed vertex cover approximation (Kuhn et al. in JACM 63:116, 2016). Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized O(a(2)) approximation in O(log n) rounds (Lenzen et al. in International symposium on distributed computing, Springer, 2010), a deterministic O(a log ?) approximation in O(log A) rounds (Lenzen et al. in international symposium on distributed computing, Springer, 2010), a deterministic O(a) approximation in O(log(2)?) rounds (implicit in Bansal et al. in Inform Process Lett 122:21-24, 2017; Proceeding 17th symposium on discrete algorithms (SODA), 2006), and a randomized O(a) approximation in O(a log n) rounds (Morgan et al. in 35th International symposiumon distributed computing, 2021). We also provide a randomized O(a log ?) round distributed algorithm that sharpens the approximation factor to a (1 + o(1)). If each node is restricted to do polynomial-time computations, our approximation factor is tight in the first order as it is NP-hard to achieve a - 1 - e approximation (Bansal et al. in Inform Process Lett 122:21-24, 2017). Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-b-000615188Publikationsstatus
publishedExterne Links
Zeitschrift / Serie
Distributed ComputingVerlag
SpringerThema
Distributed computing; Dominating set; Arboricity; Approximation algorithmsFörderung
853109 - Distributed and Massively Parallel Graph Algorithms (EC)
184735 - Distributed Algorithms for Global Graph Problems (SNF)
ETH Bibliographie
yes
Altmetrics