New Algorithms for Maximum Weight Matching and a Decomposition Theorem
- 1 May 2017
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 42 (2) , 411-426
Abstract
We revisit the classical maximum weight matching problem in general graphs with nonnegative integral edge weights. We present an algorithm that operates by decomposing the problem into W unweighted versions of the problem, where W is the largest edge weight. Our algorithm has running time as good as the current fastest algorithms for the maximum weight matching problem when W is small. One of the highlights of our algorithm is that it also produces an integral optimal dual solution; thus our algorithm also returns an integral certificate corresponding to the maximum weight matching that was computed. Our algorithm yields a new proof to the total dual integrality of Edmonds’ matching polytope and it also gives rise to a decomposition theorem for the maximum weight of a matching in terms of the maximum size of a matching in certain subgraphs. We also consider the maximum weight capacitated b-matching problem in bipartite graphs with nonnegative integral edge weights and show that it can also be decomposed into W unweighted versions of the problem, where W is the largest edge weight. Our second algorithm is competitive with known algorithms when W is small.Keywords
This publication has 33 references indexed in Scilit:
- Faster scaling algorithms for general graph matching problemsJournal of the ACM, 1991
- Scaling algorithms for network problemsJournal of Computer and System Sciences, 1985
- Short proofs on the matching polyhedronJournal of Combinatorial Theory, Series B, 1983
- A shortest augmenting path method for solving minimal perfect matching problemsNetworks, 1981
- A primal algorithm for optimum matching1978
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965
- Coverings of Bipartite GraphsCanadian Journal of Mathematics, 1958
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955
- The Factorization of Linear GraphsJournal of the London Mathematical Society, 1947