An easy subexponential bound for online chain partitioning
classification
💻 cs.DS
math.CO
keywords
onlinepartitioningbosekchainkrawczykworkalgorithmapproach
read the original abstract
Bosek and Krawczyk exhibited an online algorithm for partitioning an online poset of width $w$ into $w^{14\lg w}$ chains. We improve this to $w^{6.5 \lg w + 7}$ with a simpler and shorter proof by combining the work of Bosek & Krawczyk with work of Kierstead & Smith on First-Fit chain partitioning of ladder-free posets. We also provide examples illustrating the limits of our approach.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.