Please use this identifier to cite or link to this item: https://open.uns.ac.rs/handle/123456789/11952
DC FieldValueLanguage
dc.contributor.authorGiesen J.en_US
dc.contributor.authorSchuberth E.en_US
dc.contributor.authorStojaković, Milošen_US
dc.date.accessioned2020-03-03T14:46:37Z-
dc.date.available2020-03-03T14:46:37Z-
dc.date.issued2009-03-09-
dc.identifier.issn01692968en_US
dc.identifier.urihttps://open.uns.ac.rs/handle/123456789/11952-
dc.description.abstractWe 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.ispartofFundamenta Informaticaeen
dc.titleApproximate sortingen_US
dc.typeJournal/Magazine Articleen_US
dc.identifier.doi10.3233/FI-2009-0005-
dc.identifier.scopus2-s2.0-61449176984-
dc.identifier.urlhttps://api.elsevier.com/content/abstract/scopus_id/61449176984-
dc.description.versionUnknownen_US
dc.relation.lastpage72en
dc.relation.firstpage67en
dc.relation.issue1-2en
dc.relation.volume90en
item.grantfulltextnone-
item.fulltextNo Fulltext-
crisitem.author.deptPrirodno-matematički fakultet, Departman za matematiku i informatiku-
crisitem.author.orcid0000-0002-2545-8849-
crisitem.author.parentorgPrirodno-matematički fakultet-
Appears in Collections:PMF Publikacije/Publications
Show simple item record

SCOPUSTM   
Citations

9
checked on May 10, 2024

Page view(s)

18
Last Week
18
Last month
0
checked on May 3, 2024

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.