2002/05/06 by Jobst Heitzig, Heitzig, Jobst
Computer Science · Mathematics · #06A07 #11Y16 #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #cs.CC #math.CO #math.OC #msc:06A07 #msc:11Y16 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.math/0205049
arxiv created 2002/05/06 · openalex publication_date 2002/05/06 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The 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.