Supplementary: Batch Active Learning via Coordinated Matching
Javad Azimi, Alan Fern, Xiaoli Z. Fern, Glencora Borradaile, Brent Heeringa · 1993
1. Fast Updated Hungarian We show how, given a min-cost matching M in the complete bipartite graph G on vertex sets μ and S (with |S| < |μ|) how to update the min-cost matching when vertex x is deleted from μ. Of course, if x is not used in M , the matching does not change. The two most common and asymptotically most efficient algorithms for computing a minimum-cost matching are the successive-shortest-path and Hungarian algorithms. Both algorithms maintain: