On Two-Pass Streaming Algorithms for Maximum Bipartite Matching
On Two-Pass Streaming Algorithms for Maximum Bipartite Matching
复制标题
最大二分匹配的双通道流算法
DOI：
10.4230/lipics.approx/random.2021.19
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kheeran K. Naidu
中科院分区：
文献类型：
--
作者：
C. Konrad;Kheeran K. Naidu
我们研究了最大二部匹配(MBM)的两遍流算法。所有已知的用于MBM的两遍流传输算法都以类似的方式操作：它们在第一遍中计算最大匹配，并在第二遍中找到3增加的路径，以便增加在第一遍中找到的匹配。我们的目的是探索这种方法的局限性，并确定是否可以使用当前的技术来进一步改进最先进的算法。我们给出了如下结果：我们证明了每一个只计算第一遍最大匹配并输出$(2/3+\epsilon)$-近似的两遍流算法需要$n^{1+\omegga(FRAC{1}{\log\log n})}$空间，其中$n$是输入图的顶点数。这一结果是通过扩展[GKK，SODA‘12]的Ruzsa-Szemer\’{e}di图结构来获得的，以确保得到的图具有接近完美匹配，这是我们构造所需的关键性质。这一结果可能具有独立的利益。此外，我们结合了两种主要技术，即先进行二次抽样，然后是贪婪匹配算法[Konrad，MFCS‘18]，它给出了一个$2-\Sqrt{2}\约0.5857$-近似，以及计算{次数有界半匹配}[EHM，ICDMW’16][KT，约‘17]，它给出了一个$\FRAC{1}{2}+\FRAC{1}{12}\约0.5833$-近似，并得到了一个作为特例产生Konrad和Esfan diari等人’S‘算法的元算法。这统一了两个研究方向。通过优化参数，我们发现Konrad的算法对于隐含的算法类是最优的，也许令人惊讶的是，存在第二个最优算法。我们表明，我们的元算法的分析是最有可能的。我们的结果表明，如果可能的话，进一步的改进需要新的技术。
We study two-pass streaming algorithms for Maximum Bipartite Matching (MBM). All known two-pass streaming algorithms for MBM operate in a similar fashion: They compute a maximal matching in the first pass and find 3-augmenting paths in the second in order to augment the matching found in the first pass. Our aim is to explore the limitations of this approach and to determine whether current techniques can be used to further improve the state-of-the-art algorithms. We give the following results: We show that every two-pass streaming algorithm that solely computes a maximal matching in the first pass and outputs a $(2/3+\epsilon)$-approximation requires $n^{1+\Omega(\frac{1}{\log \log n})}$ space, for every $\epsilon>0$, where $n$ is the number of vertices of the input graph. This result is obtained by extending the Ruzsa-Szemer\'{e}di graph construction of [GKK, SODA'12] so as to ensure that the resulting graph has a close to perfect matching, the key property needed in our construction. This result may be of independent interest. Furthermore, we combine the two main techniques, i.e., subsampling followed by the Greedy matching algorithm [Konrad, MFCS'18] which gives a $2-\sqrt{2} \approx 0.5857$-approximation, and the computation of \emph{degree-bounded semi-matchings} [EHM, ICDMW'16][KT, APPROX'17] which gives a $\frac{1}{2} + \frac{1}{12} \approx 0.5833$-approximation, and obtain a meta-algorithm that yields Konrad's and Esfandiari et al.'s algorithms as special cases. This unifies two strands of research. By optimizing parameters, we discover that Konrad's algorithm is optimal for the implied class of algorithms and, perhaps surprisingly, that there is a second optimal algorithm. We show that the analysis of our meta-algorithm is best possible. Our results imply that further improvements, if possible, require new techniques.
图形流上两次、三次以及更多次的最大匹配
DOI：
10.4230/lipics.approx-random.2017.15
发表时间：
2017
期刊：
and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
作者：
Kale, Sagar;Tirodkar, Sumedh
通讯作者：
Tirodkar, Sumedh
随机顺序流匹配击败三分之二
DOI：
10.4230/lipics.icalp.2021.19
发表时间：
2021
期刊：
Scotland (Virtual Conference
影响因子：
--
作者：
Assadi, Sepehr;Behnezhad, Soheil
通讯作者：
Behnezhad, Soheil
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