An Improved Method for Finding the K Smallest Cost Assignments in Order ; CU-CS-124-78

摘要

An assignment is a perfect matching on a bipartite graph. An algorithm is given that outputs the K smallest cost assignments in order of increasing cost. The time is 0(K min(V^3, VE log V)) and the space is 0(E+K), where V and E are the number of vertices and edges. This compares favorably to a previous algorithm with runtime 0(KV’). The speed-up is achieved by using a shortest path calculation to generate one optimal assignment from another. Two special cases of the problem are also discussed: finding all assignments in order, and finding all minimum cost assignments. The latter is done in 0(min(V^3,VE log V)+ME) time and 0€ space, where M is the number of minimum cost assignments. A previous algorithm for finding all perfect matchings is used. The algorithms extend to ranking maximum matchings. The closely related problems of finding the kth smallest assignment and finding an assignment of given cost C are shown NP-hard.