Tightening the upper bound for the minimum energy broadcasting

In this paper we present a new upper bound on the approximation ratio of the Minimum Spanning Tree heuristic for the basic problem on Ad-Hoc Networks given by the Minimum Energy Broadcast Routing (MEBR). We introduce a new analysis allowing to establish a 6.33-approximation ratio in the 2-dimensional case, thus decreasing the previously known 7.6 upper bound [4], almost closing the gap with the lower bound of 6 [12]. Preliminary results concerning this paper appeared in [9]. Michele Flammini received the degree in Computer Science at the University of L’Aquila in 1990 and the Ph.D. degree in Computer Science at the University of Rome “La Sapienza” in 1995. He is full professor at the Computer Science Department of the University of L’Aquila since March 2005. His research interests include algorithms and computational complexity, game theory, communication problems in interconnection networks and routing. He has authored and co-authored more than 70 papers in his fields of interest published in the most reputed international conferences and journals. Ralf Klasing received the PhD degree from the University of Paderborn in 1995. From 1995 to 1997, he was an Assistant Professor at the University of Kiel. From 1997 to 1998, he was a Research Fellow at the University of Warwick. From 1998 to 2000, he was an Assistant Professor at RWTH Aachen. From 2000 to 2002, he was a Lecturer at King’s College London. In 2002, he joined the CNRS as a permanent researcher. From 2002 to 2005, he was affiliated to the laboratory I3S in Sophia Antipolis. Currently, he is affiliated to the laboratory LaBRI in Bordeaux. He has co-authored a Springer Monograph, a book chapter, and has published more than 40 papers in refereed international periodicals. His research interests include Communication Algorithms in Networks, Approximation Algorithms for Combinatorially Hard Problems, Web Graphs and Web Algorithms, and Optimization Problems in Ad-Hoc Wireless Networks. Alfredo Navarra received the degree in Computer Science at the University of L’Aquila in 2000 and the Ph.D. degree in Computer Science at the University of Rome “La Sapienza” in 2004. From 2003 to 2004, he joined the MASCOTTE project team at the INRIA institute of Sophia Antipolis as PhD student and PostDoc for almost two years. In 2005, he was a temporary researcher at the University of L’Aquila. In 2006, he joined the laboratory LaBRI in Bordeaux as PostDoc. His research interests include, algorithms and computational complexity, communication, modelling as well as analysis and experimentation problems on protocols and routing algorithms for interconnaction networks such as Ad Hoc, Wireless, Mobile and Sensor Networks. He has authored and co-authored more than 25 papers in his fields of interest published in the most reputed international conferences and journals. Stéphane Pérennes is a permanent researcher of the French Centre National de la Recherche Scientifique (CNRS). He is affiliated to the MASCOTTE project team at the Institut National de Recherche en Informatique et Automatique (INRIA) of Sophia Antipolis. He has authored and co-authored more than 70 papers in his fields of interest that vary from pure theoretical to applied issues on algorithms and complexity, networking and routing.