Speaker
Description
Summary
Recentely, a new greedy algorithm for approximating minimum set cover has been
presented (see SIGEF Congress New Logistics for the new economy" Naples Italy 2001).
The algorithm while not randomized, is based os a probability distribution that leads
the greedy choice.
It shows very good empirical performances and it has succesfully been applied in
wireless network applications, where greedy algorithm for set cover produce sets of
nodes that can be used to form a virtual backbone.
Tha cost o f probability distribution evaluation can still be unaffordable in real-time
applications.
In this paper we describe a version of the algorithm that has been specifically
tailored to run on platforms with minimal hardware.
Together with the algorithm description we describe an hardware demostrator we
developped and the results we obtained.
