Min cost flow on unit capacity networks and convex cost K-flow are as easy as the assignment problem with All-Min-Cuts algorithm.

Dorit S. Hochbaum

Published in: CoRR (2016)

Keyphrases

min cost
max flow
network flow
combinatorial optimization problems
np hard
parallel processors
dynamic programming
worst case
simulated annealing
objective function
minimum cost
globally optimal
knapsack problem
convex relaxation
cost function
search space
optimal solution