Nested Partitioning for the Minimum Energy Broadcast Problem

In: LION~II: Learning and Intelligent OptimizatioN Conference. LNCS, Won a Best Paper Award. Post-Proceedings still to be published, 2008

Authors

• Sameh Al-Shihabi
• Peter Merz
• Steffen Wolf

Abstract

The problem of finding the broadcast scheme with minimum power consumption in a wireless ad-hoc network is NP-hard. This work presents a new hybrid algorithm to solve this problem by combining Nested Partitioning with Local Search and Linear Programming. The algorithm is benchmarked by solving instances with 20 and 50 nodes where results are compared to either optimum or best results found by an IP solver. In these instances, the proposed algorithm was able to find optimal and near optimal solutions.

BibTeX

 
@InProceedings{ Shihabi2007MEBNP, 
   title = { Nested Partitioning for the Minimum Energy Broadcast Problem }, 
   author = { Sameh Al-Shihabi and Peter Merz and Steffen Wolf },   
   booktitle = { LION~II: Learning and Intelligent OptimizatioN Conference },  
   series = { LNCS },          
   note = { Won a Best Paper Award. Post-Proceedings still to be published },  
   year = 2008, 
} 

---

This publication belongs to the project DeNDeMA.