Approximating maximum integral flows in wireless sensor networks via weighted-degree constrained k-flows

We consider the Maximum Integral Flow with Energy Constraints problem: given a directed graph G = (V, E) with edge-weights {w(e) : e G E} and node battery capacities {b(v) : v G V}, and two nodes r, s G V, find a maximum integral rs-flow f so that for every node v its energy consumption P _vueEf(vu)w(vu) is at most b(v). Let k be the maximum integral flow value. We give a polynomial time algorithm that computes a flow of value at least [k/16\. As checking whether k > 1 can be done in polynomial time, this gives an approximation algorithm with ratio that approaches 1/16 when k is large, and is not worse than 1/31. This is the first constant ratio approximation algorithm for this problem, which solves an open question from [2]. This result is based on a bicriteria approximation algorithm for a more general problem, in which we seek a minimum cost set of k pairwise edge-disjoint rs-paths (that is, a k-flow) subject to weighted degree constraints. We give a polynomial time algorithm that computes a flow of value k and violates the weighted degrees by a factor at most 4. This result is of independent interest.