TR-2007-09

Degree constrained submodular flows

Tamás Király, Lap Chi Lau



Abstract

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:

@techreport{egres-07-09,
AUTHOR = {Kir{\'a}ly, Tam{\'a}s and Lau Chi, Lap},
TITLE = {Degree constrained submodular flows},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2007},
NUMBER = {TR-2007-09}
}


Last modification: 5.6.2018. Please email your comments to Tamás Király!