An easy subexponential bound for online chain partitioning

Bartłomiej Bosek, Hal A. Kierstead, Tomasz Krawczyk +2

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…