On the complexity and approximability of budget-constrained minimum cost flows.

Michael Holzhauser Sven O. Krumke Clemens Thielen

Published in: Inf. Process. Lett. (2017)

Keyphrases

minimum cost
approximation algorithms
np hard
worst case
network flow
spanning tree
network flow problem
capacity constraints
network simplex algorithm
special case
approximation ratio
minimum cost flow
primal dual
edit operations
optimal solution
linear programming