论文标题
分区最小加权匹配问题的有效算法
An Efficient Algorithm for the Partitioning Min-Max Weighted Matching Problem
论文作者
论文摘要
分区最大加权匹配（PMMWM）问题是一个NP硬质问题，它结合了将两部分图的一组顶点分配到有限尺寸和经典的Min-Max加权匹配（MMWM）问题的问题的问题。 Kress等。在2015年提出了这个问题，他们还提供了几种算法，其中MP $ _ {\ text {ls}} $是最新的。在这项工作中，我们观察到MP $ _ {\ text {ls}} $的匹配阶段中有一个时间瓶颈。因此，我们在匹配迭代期间优化了冗余操作，并提出了一种称为MP $ _ {\ text {km-m}} $的有效算法，该算法极大地加速了MP $ _ {\ text {ls {ls}} $。瓶颈时间复杂性从$ O（n^3）$到$ O（n^2）$优化。我们还通过Primal Dual方法证明了MP $ _ {\ text {km-m}} $的正确性。为了测试各种实例的性能，我们生成了各种类型和大小的基准，并就MP $ _ {\ text {km-m}} $和MP $ _ {\ text {\ text {ls {ls}} $进行了广泛的计算研究。评估结果表明，与MP $ _ {\ text {ls}} $相比，我们的MP $ _ {\ text {km-m}} $在产生相同的解决方案质量的同时大大缩短了运行时。
The Partitioning Min-Max Weighted Matching (PMMWM) problem is an NP-hard problem that combines the problem of partitioning a group of vertices of a bipartite graph into disjoint subsets with limited size and the classical Min-Max Weighted Matching (MMWM) problem. Kress et al. proposed this problem in 2015 and they also provided several algorithms, among which MP$_{\text{LS}}$ is the state-of-the-art. In this work, we observe there is a time bottleneck in the matching phase of MP$_{\text{LS}}$. Hence, we optimize the redundant operations during the matching iterations, and propose an efficient algorithm called the MP$_{\text{KM-M}}$ that greatly speeds up MP$_{\text{LS}}$. The bottleneck time complexity is optimized from $O(n^3)$ to $O(n^2)$. We also prove the correctness of MP$_{\text{KM-M}}$ by the primal-dual method. To test the performance on diverse instances, we generate various types and sizes of benchmarks, and carried out an extensive computational study on the performance of MP$_{\text{KM-M}}$ and MP$_{\text{LS}}$. The evaluation results show that our MP$_{\text{KM-M}}$ greatly shortens the runtime as compared with MP$_{\text{LS}}$ while yielding the same solution quality.
