Improved lower bounds on the on-line chain partitioning of posets of bounded dimension
From MaRDI portal
Publication:6139864
DOI10.1007/S11083-023-09629-7arXiv2111.04802OpenAlexW4361283673MaRDI QIDQ6139864
Publication date: 19 December 2023
Published in: Order (Search for Journal in Brave)
Abstract: 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'edi proved that any on-line algorithm could be forced to use $�inom{w+1}{2}$ 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'edi'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))�inom{w+1}{2}$ chains to partition a $2$-dimensional poset of width $w$. Second, we prove that any on-line algorithm can be forced to use $(2-frac{1}{d-1}-o(1))�inom{w+1}{2}$ chains to partition a poset of width $w$ presented via a realizer of size $d$.
Full work available at URL: https://arxiv.org/abs/2111.04802
Cites Work
This page was built for publication: Improved lower bounds on the on-line chain partitioning of posets of bounded dimension
