Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 05, 2022, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Saeed Ilchi
We describe a simple deterministic O(epsilon^-1 log Delta) round distributed algorithm for 2(alpha+1)(1+epsilon) approximation of minimum weighted dominating set on graphs with arboricity at most alpha. Here Delta 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, Moscibroda, and Wattenhofer JACM'16]. Our algorithm improves on all the previous results (that work only for unweighted graphs) including a randomized O(alpha^2) approximation in O(log n) rounds [Lenzen and Wattenhofer DISC'10], a deterministic O(alpha log Delta) approximation in O(log Delta) rounds [Lenzen and Wattenhofer DISC'10], a deterministic O(alpha) approximation in O(log^2 Delta) rounds [implicit in Bansal and Umboh IPL'17 and Kuhn, Moscibroda, and Wattenhofer SODA'06], and a randomized O(alpha) approximation in O(alpha log n) rounds [Morgan, Solomon and Wein DISC'21]. This is a joint work with Michal Dory and Mohsen Ghaffari.
Automatic MiSe System Software Version 1.4803M | admin login