On-line partitioning of width w posets into w^O(log log w) chains

Bartłomiej Bosek, Tomasz Krawczyk

An on-line chain partitioning algorithm receives the elements of a poset one at a time, and when an element is received, irrevocably assigns it to one of the chains. In this paper,…