An Efficient Algorithm for the Partitioning Min-Max Weighted Matching Problem
share
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_LS is the state-of-the-art. In this work, we observe there is a time bottleneck in the matching phase of MP_LS. Hence, we optimize the redundant operations during the matching iterations, and propose an efficient algorithm called the MP_KM-M that greatly speeds up MP_LS. The bottleneck time complexity is optimized from O(n^3) to O(n^2). We also prove the correctness of MP_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_KM-M and MP_LS. The evaluation results show that our MP_KM-M greatly shortens the runtime as compared with MP_LS while yielding the same solution quality.
READ FULL TEXT