Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, March 05, 2019, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Chih-Hung Liu
We consider the approximate minimum selection problem in presence of independent random comparison faults. This problem asks to select one of the smallest k elements in a linearly ordered collection of n elements by only performing unreliable pairwise comparisons: whenever two elements are compared, there is constant probability that the wrong answer is returned. We design a randomized algorithm that solves this problem with high probability (w.h.p.) for the whole range of values of k using O(log n · ( n/k + log log log n)) expected time. Then, we prove that the expected running time of any algorithm that succeeds w.h.p. must be Omega((n/k) log n), thus implying that our algorithm is optimal, in expectation, for almost all values of k (and it is optimal up to triple-log factors for k = omega( n/log log log n )). These results are quite surprising in the sense that for k between Omega(log n) and c · n, for any constant c < 1, the expected running time must still be Omega((n/k)log n) even in absence of comparison faults.
Automatic MiSe System Software Version 1.4803M | admin login