We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
The $k$-Equal Problem.
- Authors
AIGNER, MARTIN
- Abstract
Suppose we are given $n$ coloured balls and an integer $k$ between 2 and $n$. How many colour-comparisons $Q(n,k)$ are needed to decide whether $k$ balls have the same colour? The corresponding problem when there is an (unknown) linear order with repetitions on the balls was solved asymptotically by Björner, Lovász and Yao, the complexity being \smash{$\theta (n\log\frac{2n}{k})$}. Here we give the exact answer for \smash{$k>\frac{n}{2}: Q(n,k)=2n-k-1$}, and the order of magnitude for arbitrary \smash{$k:Q(n,k)=\theta(\frac{n^2}{k})$}.
- Publication
Combinatorics, Probability & Computing, 2005, Vol 14, Issue 1/2, p17
- ISSN
0963-5483
- Publication type
Article
- DOI
10.1017/S0963548304006704