A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs

Lyle Ramshaw, Robert E. Tarjan

Research output: Contribution to journalConference article

11 Scopus citations

Abstract

Call a bipartite graph G = (X, Y, E) balanced when |X| = |Y|. Given a balanced bipartite graph G with edge costs, the assignment problem asks for a perfect matching in G of minimum total cost. The Hungarian Method can solve assignment problems in time O(mn + n2 log n), where n := |X| = |Y| and m := |E|. If the edge weights are integers bounded in magnitude by C > 1, then algorithms using weight scaling, such as that of Gabow and Tarjan, can lower the time to O(m √n log(nC)). There are important applications in which G is unbalanced, with |X| ≠ |Y|, and we require a min-cost matching of size r := min(|X|, |Y|) or, more generally, of some specified size s ≤ r. The Hungarian Method extends easily to find such a matching in time O(ms + s2 log r), but weightscaling algorithms do not extend so easily. We introduce new machinery to find such a matching in time O(m√s log(sC)) via weight scaling. Our results provide some insight into the design space of efficient weight-scaling matching algorithms.

Original languageEnglish (US)
Article number6375337
Pages (from-to)581-590
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - Dec 1 2012
Event53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States
Duration: Oct 20 2012Oct 23 2012

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'A weight-scaling algorithm for min-cost imperfect matchings in bipartite graphs'. Together they form a unique fingerprint.

  • Cite this