Publikation
On-Line Chain Partitions of Orders: a Survey
Bartlomiej Bosek; Stefan Felsner; Kamil Kloch; Tomasz Krawczyk; Grzegorz Matecki; Piotr Micek
In: Order, Vol. 29, Pages 49-73, Springer Netherlands, 2012.
Zusammenfassung
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.