An Easy Subexponential Bound for Online Chain Partitioning

Bartłomiej Bosek, H. A. Kierstead, Tomasz Krawczyk, Grzegorz Matecki, Matthew E. Smith


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.


Partially ordered set, Poset, First-fit, Online chain partition, Ladder, Regular poset

Full Text: