We consider the problem of finding a minimum cost 0-1 submodular flow with the additional constraint that the sum of the incoming and outgoing flow at each node cannot exceed a given limit. We show that this problem is NP-hard, but it can be approximated in the following sense: we can find a submodular flow of cost not greater than the optimum which violates the additional constraints by at most 1 at every node.
Bibtex entry:
AUTHOR | = | {Kir{\'a}ly, Tam{\'a}s and Lau Chi, Lap}, |
TITLE | = | {Degree constrained submodular flows}, |
NOTE | = | {{\tt egres.elte.hu}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2007}, |
NUMBER | = | {TR-2007-09} |