ON-LINE CHAIN PARTITIONING OF UP-GROWING ORDERS: THE CASE OF 2-DIMENSIONAL ORDERS AND SEMI-ORDERS
Stefan Felsner, Kamil Kloch, Grzegorz Matecki, Piotr Micek · arXiv (Cornell University) · 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 `w+1 ´ as usual w is the width of the order. Our main contribution is 2 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 ⌊ 1+√5 w⌋. The proof 2 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. 1.