Approximation bounds for the minimum k-storage problem

Sensor networks are widely used to collect data that are required for future information retrieval. Data might be aggregated in a predefined number k of special nodes in the network, called storage nodes, which, for replying to external queries, compress the last received raw data and send them towards the sink. We consider the problem of locating such storage nodes in order to minimize the energy consumed for converging the raw data to the storage nodes as well as to converge the aggregated data to the sink. This is known as the minimum k-storage problem. We first prove that it is NP-hard to be approximated within a factor of 1+1e. We then propose a local search algorithm which guarantees a constant approximation factor. We conducted extended experiments to show that the algorithm performs very well in many different scenarios. Further, we prove that the problem is not in APX if we consider directed links, unless P=NP.