The asymptotic complexity of partial sorting -- How to learn large posets by pairwise comparisons

Simple item page
dc.creatorHeitzig, Jobst
dc.date2002-05-06
dc.date.accessioned2026-07-07T04:48:17Z
dc.date.available2026-07-07T04:48:17Z
dc.descriptionThe expected number of pairwise comparisons needed to learn a partial order on n elements is shown to be at least n*n/4-o(n*n), and an algorithm is given that needs only n*n/4+o(n*n) comparisons on average. In addition, the optimal strategy for learning a poset with four elements is presented.
dc.identifierhttps://arxiv.org/abs/math/0205049
dc.identifierhttp://arxiv.org/abs/math/0205049
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/63984
dc.subjectCombinatorics
dc.subjectComputational Complexity
dc.subjectOptimization and Control
dc.subject06A07; 11Y16
dc.titleThe asymptotic complexity of partial sorting -- How to learn large posets by pairwise comparisons
dc.typetext

Files

Collections

arXiv