On-line Chain Partitions of Up-growing Semi-orders |
| |
Authors: | Stefan Felsner Kamil Kloch Grzegorz Matecki Piotr Micek |
| |
Affiliation: | 1. AG Diskrete Mathematik Institut für Mathematik, Technische Universit?t Berlin, Strasse des 17. Juni 136, 10623, Berlin, Germany 2. Embedded Systems Lab, University of Passau, Innstrasse 43, 94032, Passau, Germany 3. Theoretical Computer Science Department, Jagiellonian University, Lojasiewicza 6, 30-348, Kraków, Poland
|
| |
Abstract: | On-line chain partition is a two-player game between Spoiler and Algorithm. Spoiler presents a partially ordered set, point by point. 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. We analyze the chain partition game for up-growing semi-orders. Surprisingly, the golden ratio comes into play and the value of the game is $\big\lfloor\frac{1+\sqrt{5}}{2} w \big\rfloor$ . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|