An easy subexponential bound for online chain partitioning
arXiv:1410.3247
Abstract
Bosek and Krawczyk exhibited an online algorithm for partitioning an online poset of width into chains. We improve this to 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.
23 pages, 11 figures