| On-line chain partitioning of up-growing orders: The case of 2-dimensional orders and semi-orders (2007) | |||||||||
Abstract | |||||||||
| We analyze special cases of the on-line chain partition problem of up-growing orders. One result is a lower bound for 2-dimensional orders. Together with the old upper bound this yields the precise value of this game which is $\binom{w+1}{2}$ as usual $w$ is the width of the order. Our main contribution is the analysis of the game for semi-orders. Surprisingly the golden ratio comes into play, the precise value of the game for width $w$ is $\lfloor\frac{1+\sqrt{5}}{2} w \rfloor$. The proof of the upper bound is based on a quite unusual twist in perspective. It is established by showing that against a natural algorithm the best strategy is the strategy provided by the lower bound construction. | |||||||||
Publication details | |||||||||
| |||||||||