On the Complexity and Approximability of Budget-Constrained Minimum Cost Flows.

Michael Holzhauser Sven O. Krumke Clemens Thielen

Published in: CoRR (2016)

Keyphrases

minimum cost
approximation algorithms
np hard
worst case
network flow
network flow problem
spanning tree
capacity constraints
network simplex algorithm
computational complexity
special case
undirected graph
minimum cost flow
approximation ratio
minimum cost path