STATISTICS AND OR SEMINAR
PROBABILISTIC EXISTENCE THEOREMS IN DISCRETE
SEARCH: SEARCH WITH LIES
Anatoly Zhigljavsky
On a number of simple examples including group testing, this seminar
introduces the basic ideas of the subject of the probabilistic method in
discrete search. A proof of some results for the problem of group testing
with lies is outlined. To establish asymptotical properties of the upper
bounds for the group search with lies, inequalities for the so-called
Lambert W-function are derived. One of the main results is somehow
counter-intuitive: the second term in the asymptotics typically dominates
the main term (even for very large problems).
16.00 Wednesday, October 16, 2002
Cardiff University, Mathematics, Senghennydd Road, Room
M/0.37
|