Evolutionary Local Search for the Super-Peer Selection Problem and the p-Hub Median Problem

In: Thomas Bartz-Beielstein and others ed., Hybrid Metaheuristics, Proceedings. LNCS, Volume 4771, Springer, P. 1--15, 2007

Authors

• Steffen Wolf
• Peter Merz

Abstract

Scalability constitutes a key property in Peer-to-Peer environments. One way to foster this property is the introduction of super-peers, a concept which has gained widespread acceptance in recent years. However, the problem of finding the set of super-peers that minimizes the total communication cost is NP-hard. We present a new heuristic based on Evolutionary Techniques and Local Search to solve this problem. Using actual Internet distance measurements, we demonstrate the savings in total communication cost attainable by such a super-peer topology. Our heuristic can also be applied to the more general Uncapacitated Single Assignment p-Hub Median Problem. The Local Search is then further enhanced by generalized don't look bits. We show that our heuristic is competitive with other heuristics even in this general problem, and present new best solutions for the largest instances in the well known Australia Post data set.

Full Text

• Publication: Wolf2007SuperPeerSelection.pdf

BibTeX

 
@Proceedings{ Wolf2007SuperpeerSelection, 
   title = { Evolutionary Local Search for the Super-Peer Selection Problem and the p-Hub Median Problem }, 
   author = { Steffen Wolf and Peter Merz },  
   editor = { Thomas Bartz-Beielstein and others }, 
   booktitle = { Hybrid Metaheuristics, Proceedings },  
   series = { LNCS }, 
   volume = { 4771 },     
   publisher = { Springer },   
   pages = { 1--15 },   
   year = 2007, 
} 

---

This publication belongs to the project DeNDeMA.