We consider the problem of maximizing the lifetime of sensor networks with data aggregation, which was previously investigated by Kalpakis et al. [1]. They propose an exact polynomial-time algorithm, which however is very slow - O n15 logn , and faster heuristics.

In this paper, we demonstrate an alternative approach based on the Garg-K ?onemann algorithm [2] for packing linear programs, combined with the exact computation of minimum cost arborescence. For any \varepsilon \gt 0, our approach obtains a solution achieving at least 1 - \varepsilon times the optimum lifetime, with running time o(n^3 \frac{1} {\varepsilon }\log 1 + \varepsilon ^n ).

The simulation result shows that our algorithm achieves a solution that is within 2.5% of optimum and is not slower than the heuristics previously proposed by Kalpakis et al.