Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/11952
Title: | Approximate sorting | Authors: | Giesen J. Schuberth E. Stojaković, Miloš |
Issue Date: | 9-Mar-2009 | Journal: | Fundamenta Informaticae | Abstract: | We show that any comparison based, randomized algorithm to approximate any given ranking of n items within expected Spearman's footrule distance n^{2}/ν(n) needs at least n (min{log ν(n), log n} - 6) comparisons in the worst case. This bound is tight up to a constant factor since there exists a deterministic algorithm that shows that 6n log (n) comparisons are always sufficient. | URI: | https://open.uns.ac.rs/handle/123456789/11952 | ISSN: | 01692968 | DOI: | 10.3233/FI-2009-0005 |
Appears in Collections: | PMF Publikacije/Publications |
Show full item record
SCOPUSTM
Citations
9
checked on May 10, 2024
Page view(s)
18
Last Week
18
18
Last month
0
0
checked on May 3, 2024
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.