Reports
An Improved Method for Finding the K Smallest Cost Assignments in Order ; CU-CS-124-78 Public Deposited
https://scholar.colorado.edu/concern/reports/9p290b33r
- Abstract
- 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.
- Creator
- Date Issued
- 1977-09-01
- Academic Affiliation
- Last Modified
- 2019-12-21
- Resource Type
- Rights Statement
- Language
Relationships
Items
| Thumbnail | Title | Date Uploaded | Visibility | Actions |
|---|---|---|---|---|
|
|
anImprovedMethodForFindingTheKSmallestCostAssignmentsIn.pdf | 2019-12-21 | Public | Download |