Finding the Best Solutions: The Cost of ls C Problem and Finding Matchings ; CU-CS-139-78

Reports

Citations

Citeable URL: https://scholar.colorado.edu/concern/reports/wh246s85s

Abstract

For a given combinatorial optimization problem, the corresponding COST≤C problem is to find all solutions of cost at most C. This is closely related to the often-studied K BEST problem, which is to find the K smallest solutions in order. Typical COST≤C algorithms for graph problems (e.g., paths, matchings, spanning trees) use less space (0(m+n) instead of 0(K+m+n)) than K BEST, and are slightly faster. As an illustration, several COST≤C (and K BEST) algorithms for matchings on bipartite graphs are presented. The times are 0(K min(n^3, mn log n)), improving previous bounds. Theapproach is to reduce the matching problems to path problems on directed graphs. Lastly, a justification is given for the relatively high time bound on COST≤C for paths: A single-source problem arising in its solution is shown to be equivalent to a multi-source problem.

Creator