The Complexity of Finding Replicas Using Equality Tests
DOI:
https://doi.org/10.7146/dpb.v22i437.6754Resumé
We prove (for fixed k) that at least (1/k - 1)(^n_2) - O(n) equality tests and no more than (2/k)(^n_2) + O(n) equality tests are needed in the worst case to determine whether a given set of n elements contains a subset of k identical elements. The upper bound is an improvement by a factor 2 compared to known results. We give tighter bounds for k = 3.Downloads
Publiceret
1993-04-01
Citation/Eksport
Frandsen, G. S., Miltersen, P. B., & Skyum, S. (1993). The Complexity of Finding Replicas Using Equality Tests. DAIMI Report Series, 22(437). https://doi.org/10.7146/dpb.v22i437.6754
Nummer
Sektion
Articles
Licens
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.