Streaming Algorithms for Weighted k-Disjoint Matchings

We design and implement two single-pass semi-streaming algorithms for the maximum weight $k$-disjoint matching ($k$-DM) problem. Given an integer $k$, the $k$-DM problem is to find $k$ pairwise edge-disjoint matchings such that the sum of the weights of the matchings is maximized. For $k \geq 2$, this problem is NP-hard. Our first algorithm is based on the primal-dual framework of a linear programming relaxation of the problem and is $\frac{1}{3+\varepsilon}$-approximate. We also develop an approximation preserving reduction from $k$-DM to the maximum weight $b$-matching problem. Leveraging this reduction and an existing semi-streaming $b$-matching algorithm, we design a $\frac{k}{(2+\varepsilon)(k+1)}$-approximate semi-streaming algorithm for $k$-DM. For any constant $\varepsilon>0$, both of these algorithms require $O(nk \log_{1+\varepsilon}^2 n)$ bits of space. To the best of our knowledge, this is the first study of semi-streaming algorithms for the $k$-DM problem. We compare our two algorithms to state-of-the-art offline algorithms on 82 real-world and synthetic test problems. On the smaller instances, our streaming algorithms used significantly less memory (ranging from 6$\times$ to 114$\times$ less) and were faster in runtime than the offline algorithms. Our solutions were often within 5\% of the best weights from the offline algorithms. On a collection of six large graphs with a memory limit of 1 TB and with $k=8$, the offline algorithms terminated only on one graph (mycielskian20). The best offline algorithm on this instance required 640 GB of memory and 20 minutes to complete. In contrast, our slowest streaming algorithm for this instance took under four minutes and produced a matching that was 18\% better in weight, using only 1.4 GB of memory.

我们针对最大权重$k$-不相交匹配（$k$-DM）问题设计并实现了两种单遍半流式算法。给定一个整数$k$，$k$-DM问题是要找到$k$对边不相交的匹配，使得这些匹配的权重之和最大。对于$k\geq2$，该问题是NP难的。我们的第一种算法基于该问题的线性规划松弛的原始 - 对偶框架，并且是$\frac{1}{3 + \varepsilon}$ - 近似的。我们还开发了一种从$k$-DM到最大权重$b$-匹配问题的近似保持归约。利用这种归约和一种现有的半流式$b$-匹配算法，我们为$k$-DM设计了一种$\frac{k}{(2 + \varepsilon)(k + 1)}$ - 近似的半流式算法。对于任何常数$\varepsilon > 0$，这两种算法都需要$O(nk\log_{1 + \varepsilon}^2 n)$位的空间。据我们所知，这是对$k$-DM问题的半流式算法的首次研究。我们在82个真实世界和合成测试问题上，将我们的两种算法与最先进的离线算法进行了比较。在较小的实例上，我们的流式算法使用的内存显著更少（少6倍到114倍不等），并且在运行时间上比离线算法更快。我们的解通常在离线算法的最佳权重的5%以内。在一组六个内存限制为1TB且$k = 8$的大型图上，离线算法仅在一个图（mycielskian20）上终止。在此实例上，最好的离线算法需要640GB的内存和20分钟才能完成。相比之下，我们在此实例上最慢的流式算法耗时不到四分钟，仅使用1.4GB的内存就生成了权重优18%的匹配。