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 ? E and node battery capacities (b(v):v ? V), and two nodes r,s ? V, find a maximum integral rs-flow f so that for every node v its energy consumption sum vu ? E f(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.
integral flow wireless sensor networks weighted degree network design maximum flow