2021/11/08 by Csaba Bíró, Biró, Csaba, Israel R. Curbelo +1
Computer Science · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #Digital Image Processing Techniques #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2111.04802
openalex publication_date 2021/11/08 · openalex created_date 2022/10/25 · openalex updated_date 2026/07/28
An on-line chain partitioning algorithm receives a poset, one element at a time, and irrevocably assigns the element to one of the chains. Over 30 years ago, Szemerédi proved that any on-line algorithm could be forced to use \binomw+12 chains to partition a poset of width w. The maximum number of chains that can be forced on any on-line algorithm remains unknown. In a survey paper by Bosek et al., it is shown that Szemerédi's argument could be improved to obtain a lower bound almost twice as good. Variants of the problem were considered where the class is restricted to posets of bounded dimension or where the poset is presented via a realizer of size d. In this paper, we prove two results. First, we prove that any on-line algorithm can be forced to use (2-o(1))\binomw+12 chains to partition a 2-dimensional poset of width w. Second, we prove that any on-line algorithm can be forced to use (2-(1)/(d-1)-o(1))\binomw+12 chains to partition a poset of width w presented via a realizer of size d.