Paper Info
Title
Lower bounds for finding the maximum and minimum elements with k lies
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 $k$ of the comparisons might be erroneous where $k$ is a fixed constant. We prove that at least $(k+1.5)n+\Theta(k)$ comparisons are needed in the worst case thus disproving the conjecture that $(k+1+\epsilon)n$ comparisons are enough.
Year
Venue
DocType
2011
arXiv: Discrete Mathematics
Journal
Volume
ISSN
Citations 
abs/1111.3288
Acta Univ. Sapirntiae, Inform. 3, 2 (2011) 224--229
0
PageRank 
References 
Authors
0.34
5
1
Name
Order
Citations
PageRank
Dömötör Pálvölgyi120229.14