Please use this identifier to cite or link to this item:
https://open.uns.ac.rs/handle/123456789/11952
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Giesen J. | en_US |
dc.contributor.author | Schuberth E. | en_US |
dc.contributor.author | Stojaković, Miloš | en_US |
dc.date.accessioned | 2020-03-03T14:46:37Z | - |
dc.date.available | 2020-03-03T14:46:37Z | - |
dc.date.issued | 2009-03-09 | - |
dc.identifier.issn | 01692968 | en_US |
dc.identifier.uri | https://open.uns.ac.rs/handle/123456789/11952 | - |
dc.description.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. | en |
dc.relation.ispartof | Fundamenta Informaticae | en |
dc.title | Approximate sorting | en_US |
dc.type | Journal/Magazine Article | en_US |
dc.identifier.doi | 10.3233/FI-2009-0005 | - |
dc.identifier.scopus | 2-s2.0-61449176984 | - |
dc.identifier.url | https://api.elsevier.com/content/abstract/scopus_id/61449176984 | - |
dc.description.version | Unknown | en_US |
dc.relation.lastpage | 72 | en |
dc.relation.firstpage | 67 | en |
dc.relation.issue | 1-2 | en |
dc.relation.volume | 90 | en |
item.grantfulltext | none | - |
item.fulltext | No Fulltext | - |
crisitem.author.dept | Prirodno-matematički fakultet, Departman za matematiku i informatiku | - |
crisitem.author.orcid | 0000-0002-2545-8849 | - |
crisitem.author.parentorg | Prirodno-matematički fakultet | - |
Appears in Collections: | PMF Publikacije/Publications |
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.