Parameterized Distributed Algorithms
Parameterized Distributed Algorithms
复制标题
参数化分布式算法
DOI：
10.4230/lipics.disc.2019.6
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Gregory Schwartzman
中科院分区：
文献类型：
--
作者：
R. Ben;K. Kawarabayashi;Gregory Schwartzman
在这项工作中，我们发起了一个深入的研究参数化图优化问题的分布式设置。在一个参数化问题中，算法决定是否存在一个由\n {parameter} $k$限制大小的解，如果存在，它会找到一个。我们研究的基本问题，包括最小顶点覆盖（MVC），最大独立集（MaxIS），最大匹配（MaxM），和许多其他的，在这两个分布式计算模型的ESTA和CONGEST。我们提出了在这两个模型中解决参数化问题的轮复杂性的下限，以及最佳和接近最佳的上限。
我们的结果超出了参数化问题的范围。我们证明了上述问题的任何近似算法都必须进行$\Omega（\displaystyle\Omega ^{-1}）$轮。结合[GKM 17]的算法和[KMW 16]的$\Omega（\sqrt{\frac{\log n}{\log\log n}}）$下界，将$（1+\frac）$-逼近MVC、MaxM和MaxIS的复杂度降到了$（\frac ^{-1}\log n）^{\Theta（1）}$。我们还表明，我们的参数化方法减少了精确和近似的MVC和MaxM的CONGEST算法的运行时间，如果最佳解决方案是小的，事先不知道它的大小。最后，我们提出了第一个确定性的$o（n^2）$轮CONGEST算法，该算法在严格小于2 $的因子内近似MVC和MaxM。
In this work, we initiate a thorough study of parameterized graph optimization problems in the distributed setting. In a parameterized problem, an algorithm decides whether a solution of size bounded by a \emph{parameter} $k$ exists and if so, it finds one. We study fundamental problems, including Minimum Vertex Cover (MVC), Maximum Independent Set (MaxIS), Maximum Matching (MaxM), and many others, in both the LOCAL and CONGEST distributed computation models. We present lower bounds for the round complexity of solving parameterized problems in both models, together with optimal and near-optimal upper bounds.
Our results extend beyond the scope of parameterized problems. We show that any LOCAL $(1+\epsilon)$-approximation algorithm for the above problems must take $\Omega(\epsilon^{-1})$ rounds. Joined with the algorithm of [GKM17] and the $\Omega(\sqrt{\frac{\log n}{\log\log n}})$ lower bound of [KMW16], this settles the complexity of $(1+\epsilon)$-approximating MVC, MaxM and MaxIS at $(\epsilon^{-1}\log n)^{\Theta(1)}$. We also show that our parameterized approach reduces the runtime of exact and approximate CONGEST algorithms for MVC and MaxM if the optimal solution is small, without knowing its size beforehand. Finally, we propose the first deterministic $o(n^2)$ rounds CONGEST algorithms that approximate MVC and MaxM within a factor strictly smaller than $2$.
参数化流：最大匹配和顶点覆盖
DOI：
10.1137/1.9781611973730.82
发表时间：
2015
期刊：
影响因子：
--
作者：
Rajesh Hemant Chitnis;Graham Cormode;Mohammad Taghi Hajiaghayi;Morteza Monemizadeh
通讯作者：
Morteza Monemizadeh
少数被排除在外的网络家族承认快速分布式算法
DOI：
10.1145/3212734.3212776
发表时间：
2018
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Haeupler, Bernhard;Li, Jason;Zuzic, Goran
通讯作者：
Zuzic, Goran
DOI：
10.1137/1.9781611974331.ch92
发表时间：
2016-01
期刊：
--
影响因子：
--
作者：
R. Chitnis;Graham Cormode;Hossein Esfandiari;M. Hajiaghayi;A. Mcgregor;M. Monemizadeh;Sofya Vorotnikova
通讯作者：
R. Chitnis;Graham Cormode;Hossein Esfandiari;M. Hajiaghayi;A. Mcgregor;M. Monemizadeh;Sofya Vorotnikova