On-Line Chain Partitions of Orders: a Survey

Bartlomiej Bosek, Stefan Felsner, Kamil Kloch, Tomasz Krawczyk, Grzegorz Matecki, Piotr Micek

In: Order 29 Seiten 49-73 Springer Netherlands 2012.


On-line chain partition is a two-player game between Spoiler and Algorithm. Spoiler presents, point by point, a partially ordered set. Algorithm assigns incoming points (immediately and irrevocably) to the chains which constitute a chain partition of the order. The value of the game for orders of width w is a minimum number val(w) such that Algorithm has a strategy using at most val(w) chains on orders of width at most w. There are many recent results about variants of the general on-line chain partition problem. With this survey we attempt to give an overview over the state of the art in this field. As particularly interesting aspects of the article we see: - The sketch of the proof for the new sub-exponential upper bound of Bosek and Krawczyk: Val(w)<= w (16 lg(w)). - The new lower bound: Val(w)>= (2-o(1))\binom(w+1)(2). - The inclusion of some simplified proofs of previously published results. - The comprehensive account on variants of the problem for interval orders. - The new lower bound for 2-dimensional up-growing orders.

survey.pdf (pdf, 325 KB )

Deutsches Forschungszentrum für Künstliche Intelligenz
German Research Center for Artificial Intelligence