Seminar by Cristina Pinotti: "The Minimum k-Storage Problem: complexity, approximation and experimental analysis"

17 April 2015

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+1/e. 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, and we give exact algorithms for directed paths.

M. Cristina Pinotti received the Dr. degree cum laude in Computer Science from the University of Pisa, Italy, in 1986.
During 1987-1999 she was a Researcher with the National Council of Research at the Istituto di Elaborazione dell'Informazione, Pisa.
From 2000-2003, she was an Associate Professor of Computer Science at University of Trento.
Since 2004, she is a Full Professor of Computer Science at the University of Perugia.
In 2013, she shortly visited the Department of Computer Science and Engineering, Aalto University School of Science at Helsinki.
In 2009, she visited the Dept. of Computer Science of the University of Texas at Arlington.
In 2007, she was invited at the Laboratoire d'Informatique de Paris-Nord, University Paris 13.
In 1997 and 1998, she visited the Department of Computer Science, Old Dominion University, Norfolk, VA (USA).
In 1994 and 1995 she was a Research Associate at the Department of Computers Sciences, University of North Texas, Denton, TX.
Her current research interests are in wireless networks, sensor networks, networking and energy constraints, content delivery in radio networks, design and analysis of algorithms, cellular networks, and parallel and distributed architectures.
She has published more than 100 articles in international journals, international conferences and workshops. She has been a guest co-editor for special issues in Mobile Networks and Applications, Wireless Networks, Journal of Parallel and Distributed Computing, Signal Processing, and International Journal of Vehicular Technology in the area of algorithms for wireless, ad-hoc, sensor and vehicular networks.
She has been member of the editorial board of IEEE Transactions on Parallel and Distributed Systems. She served in the program committee of 30+ international conferences and workshop, mainly in the networking area, in the last five years.