Ran Duan
Skip Abstract Section
Abstract
We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in O(m√nlog(nN)) time, O(m√ n) per scale, which matches the running time of the best cardinality matching algorithms on sparse graphs [16, 20, 36, 37]. Here, m,n, and N bound the number of edges, vertices, and magnitude, respectively, of any integer edge weight. Our result improves on a 25-year-old algorithm of Gabow and Tarjan, which runs in O(m√nlog nα (m,n) log(nN)) time.
- G. Birkhoff. 1946. Tres observaciones sobre el elgebra lineal. Universidad Nacional de Tucuman, Revista A 5, 1--2, 147--151.Google Scholar
- M. B. Cohen, A. Madry, P. Sankowski, and A. Vladu. 2017. Negative-weight shortest paths and unit capacity minimum cost flow in time. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17). 752--771. Google ScholarDigital Library
- W. H. Cunningham and A. B. Marsh, III. 1978. A primal algorithm for optimum matching. Math. Program. Study 8, 50--72.Google ScholarCross Ref
- M. Cygan, H. N. Gabow, and P. Sankowski. 2015. Algorithmic applications of Baur-Strassen’s theorem: Shortest cycles, diameter, and matchings. J. ACM 62, 4, 28. Google ScholarDigital Library
- R. Duan and S. Pettie. 2014. Linear-time approximation for maximum weight matching. J. ACM 61, 1, 1. Google ScholarDigital Library
- R. Duan and H.-H. Su. 2012. A scaling algorithm for maximum weight matching in bipartite graphs. In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 1413--1424. Google ScholarDigital Library
- J. Edmonds. 1965. Maximum matching and a polyhedron with -vertices. J. Res. Nat. Bur. Stand. Sect. B 69B, 125--130.Google ScholarCross Ref
- J. Edmonds 1965. Paths, trees, and flowers. Can. J. Math. 17, 449--467.Google ScholarCross Ref
- J. Edmonds and R. M. Karp 1972. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 2, 248--264. Google ScholarDigital Library
- M. L. Fredman and R. E. Tarjan. 1987. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34, 3, 596--615. Google ScholarDigital Library
- M. L. Fredman and D. E. Willard. 1994. Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48, 3, 533--551. Google ScholarDigital Library
- H. N. Gabow. 1976. An efficient implementation of Edmonds’ algorithm for maximum matching on graphs. J. ACM 23, 221--234. Google ScholarDigital Library
- H. N. Gabow. 1985. A scaling algorithm for weighted matching on general graphs. In Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS’85). 90--100. Google ScholarDigital Library
- H. N. Gabow. 1990. Data structures for weighted matching and nearest common ancestors with linking. In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’90). 434--443. Google ScholarDigital Library
- H. N. Gabow. 2016. Data structures for weighted matching and extensions to -matching and -factors. CoRR, abs/1611.07541.Google Scholar
- H. N. Gabow. 2017. The weighted matching approach to maximum cardinality matching. Fundam. Inform. 154, 1--4, 109--130.Google ScholarCross Ref
- H. N. Gabow, Z. Galil, and T. H. Spencer. 1989. Efficient implementation of graph algorithms using contraction. J. ACM 36, 3, 540--572. Google ScholarDigital Library
- H. N. Gabow and R. E. Tarjan. 1985. A linear-time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 2, 209--221.Google ScholarCross Ref
- H. N. Gabow and R. E. Tarjan. 1989. Faster scaling algorithms for network problems. SIAM J. Comput. 18, 5, 1013--1036. Google ScholarDigital Library
- H. N. Gabow and R. E. Tarjan. 1991. Faster scaling algorithms for general graph-matching problems. J. ACM 38, 4, 815--853. Google ScholarDigital Library
- Z. Galil, S. Micali, and H. N. Gabow. 1986. An algorithm for finding a maximal weighted matching in general graphs. SIAM J. Comput. 15, 1, 120--130. Google ScholarDigital Library
- A. V. Goldberg and R. Kennedy. 1997. Global price updates help. SIAM J. Discr. Math. 10, 4, 551--572. Google ScholarDigital Library
- Y. Han. 2002. Deterministic sorting in time and linear space. In Proceedings of the 34th ACM Symposium on Theory of Computers (STOC’02). ACM Press, 602--608. Google ScholarDigital Library
- Y. Han and M. Thorup. 2002. Integer sorting in O(n√log log n) expected time and linear space. In Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS’02). 135--144. Google ScholarDigital Library
- C.-C. Huang and T. Kavitha. 2012. Efficient algorithms for maximum weight matchings in general graphs with small edge weights. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’12). 1400--1412. Google ScholarDigital Library
- M.-Y. Kao, T. W. Lam, W.-K. Sung, and H.-F. Ting. 2001. A decomposition theorem for maximum weight bipartite matchings. SIAM J. Comput. 31, 1, 18--26. Google ScholarDigital Library
- A. V. Karzanov. 1976. Efficient implementations of Edmonds’ algorithms for finding matchings with maximum cardinality and maximum weight. In Studies in Discrete Optimization, A. A. Fridman (Eds.). Nauka, Moscow, 306--327.Google Scholar
- E. Lawler. 1976. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart 8 Winston, New York.Google Scholar
- S. Micali and V. Vazirani. 1980. An O(√|V| ċ |E|) algorithm for finding maximum matching in general graphs. In Proceedings of the 21st IEEE Symposium on Foundations of Computer Science (FOCS’80). 17--27. Google ScholarDigital Library
- J. B. Orlin and R. K. Ahuja. 1992. New scaling algorithms for the assignment and minimum mean cycle problems. Math. Program. 54, 41--56.Google ScholarDigital Library
- S. Pettie. 2012. A simple reduction from maximum weight matching to maximum cardinality matching. Inf. Process. Lett. 112, 23, 893--898. Google ScholarDigital Library
- S. Pettie. 2015. Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. J. Graph Algor. Appl. 19, 1, 375--391.Google ScholarCross Ref
- M. Thorup. 1999. Undirected single-source shortest paths with positive integer weights in linear time. J. ACM 46, 3, 362--394. Google ScholarDigital Library
- M. Thorup. 2003. Integer priority queues with decrease key in constant time and the single source shortest paths problem. In Proceedings of the 35th ACM Symposium on Theory of Computing (STOC’03). 149--158. Google ScholarDigital Library
- M. Thorup. 2007. Equivalence between priority queues and sorting. J. ACM 54, 6. Google ScholarDigital Library
- V. V. Vazirani. 2012. An improved definition of blossoms and a simpler proof of the MV matching algorithm. CoRR, abs/1210.4594.Google Scholar
- V. V. Vazirani. 2014. A proof of the MV matching algorithm. Unpublished manuscript.Google Scholar
- J. von Neumann. 1953. A certain zero-sum two-person game equivalent to the optimal assignment problem. In Contributions to the Theory of Games, vol. II, H. W. Kuhn and A. W. Tucker (Eds.). Princeton University Press, 5--12.Google Scholar
Index Terms
- Scaling Algorithms for Weighted Matching in General Graphs
Recommendations
A framework for dynamic matching in weighted graphs
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of ComputingWe introduce a new framework for computing approximate maximum weight matchings. Our primary focus is on the fully dynamic setting, where there is a large gap between the guarantees of the best known algorithms for computing weighted and unweighted ...
Scaling algorithms for weighted matching in general graphs
SODA '17: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete AlgorithmsWe present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in [EQUATION] time, [EQUATION] per scale, which matches the running time of the best cardinality matching algorithms ...
A scaling algorithm for weighted matching on general graphs
SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer ScienceThis paper presents an algorithm for maximum matching on general graphs with integral edge weights, running in time O(n3/4m lg N), where n, m and N are the number of vertices, number of edges, and largest edge weight magnitude, respectively. The best ...
Comments