The Minimum -Storage Problem: Complexity, Approximation, and Experimental Analysis

• Published in: IEEE transactions on mobile computing 2016-07, Vol.15 (7), p.1797-1811
• Main Authors: DAngelo, Gianlorenzo, Diodati, Daniele, Navarra, Alfredo, Pinotti, Cristina M.
• Format: Magazinearticle
• Language: English
• Subjects: Algorithms
• ISSN: 1536-1233; 1558-0660
• DOI: 10.1109/TMC.2015.2475765

In a sensor network, data might be stored in so-called storage nodes, which receive raw data from other nodes, compress them, and send them toward a sink . We consider the problem of locating [Formula Omitted] storage nodes in order to minimize the energy consumed for converging the raw data to the storage nodes as well as to converge the compressed data to the sink. This is known as the minimum [Formula Omitted]-storage problem . In general, the problem is [Formula Omitted]-hard. However, we are able to devise a polynomial-time algorithm that optimally solves the problem in bounded-tree width graphs. We then characterize the minimum [Formula Omitted]-storage problem from the approximation viewpoint. We first prove that it is [Formula Omitted]-hard to be approximated within a factor smaller than [Formula Omitted]. We then propose a local search algorithm that guarantees a constant approximation factor. We conducted extended experiments to show that the algorithm performs very well, exhibiting very small deviation from the optimum and computational time. It is worth to note that our problem is a generalization to the well-known metric [Formula Omitted]-median problem and then the obtained results also hold for this case.