Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms
复制标题
动态匹配：将积分算法简化为近似最大分数算法
DOI：
10.4230/lipics.icalp.2018.7
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
David Wajc
中科院分区：
文献类型：
--
作者：
Moab Arar;S. Chechik;S. Cohen;Cliff Stein;David Wajc
我们提出了一个简单的随机降低，从完全动态的积分匹配算法到完全最大的近似最大的“分数匹配算法”。将此减少应用于最近的Bhattacharya，Henzinger，Henzinger和Nanongkai（Soda 2017）的近期分数匹配算法（Soda 2017），我们（Soda 2017）对于整体问题而言，我们的主要结果是一个随机的全动态$（2+ \ epsilon）$ - 近似的积分匹配算法，带有小polylog worst-case更新时间（2+ \ Epsilon）。由于Bhattacharya等人〜（SODA 2017），近似制度仅是一个完全动态的$（2+ \ epsilon）$ - 与最差的case Polylog更新时间相匹配（我们的算法）。对于任何常数近似比，与多项式更新的近似匹配比多项式更好。
We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic $(2+\epsilon)$-approximate integral matching algorithm with small polylog worst-case update time. For the $(2+\epsilon)$-approximation regime only a fractional fully-dynamic $(2+\epsilon)$-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al.~(SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio.