Lecture Notes in Computer Science, 2009, Volume 5564/2009, 279-291, DOI: 10.1007/978-3-642-02158-9_24

Latency Constrained Aggregation in Chain Networks Admits a PTAS

Tim Nonner and Alexander Souza

View Related Documents

Abstract

This paper studies the aggregation of messages in networks that consist of a chain of nodes, and each message is time-constrained such that it needs to be aggregated during a given time interval, called its due interval. The objective is to minimize the maximum cost incurred at any node, which is for example a concern in wireless sensor networks, where it is crucial to distribute the energy consumption as equally as possible. First, we settle the complexity of this problem by proving its NP-hardness, even for the case of unit length due intervals. Second, we give a QPTAS, which we extend to a PTAS for the special case that the lengths of the due intervals are constants. This is in particular interesting, since we prove that this problem becomes APX-hard if we consider tree networks instead of chain networks, even for the case of unit length due intervals. Specifically, we show that it cannot be approximated within 4/3 − ε for any ε> 0 , unless P=NP.

Fulltext Preview

Image of the first page of the fulltext document