|
|||||
|
|
Finding the maximum and minimum elements with one lie |
|
| Authors: | Dá niel Gerbner |
| Affiliation: | a Rényi Institute of Mathematics, Hungarian Academy of Sciences, Reáltanoda utca 13-15., 1053 Budapest, Hungary b Department of Computer Science, Eötvös University, Pázmány Péter sétány 1/c, 1117 Budapest, Hungary c Department of Computer Science and Information Theory, Budapest University of Technology, 1117 Budapest, Magyar tudósok körútja 2, Hungary |
| Abstract: | In this paper we deal with the problem of finding the smallest and the largest elements of a totally ordered set of size n using pairwise comparisons if one of the comparisons might be erroneous and prove a conjecture of Aigner stating that the minimum number of comparisons needed is  for some constant c. We also address some related problems. |
| Keywords: | Search Erroneous information Sorting |
| 本文献已被 ScienceDirect 等数据库收录！ | |