On-line version of Rabinovitch theorem for proper intervals

Bartlomiej Bosek, Kamil Kloch, Tomasz Krawczyk, Piotr Micek

In: Discrete Mathematics 312 23 Seiten 3426-3436 Elsevier 2012.


We analyze the on-line dimension of semi-orders as a two-person game between Algorithm and Spoiler, in a customary way. The game is played in rounds. Spoiler presents a collection of intervals representing a semi-order, one interval at a time. Algorithm maintains its realizer, i.e., the set of linear extensions intersecting to the semi-order presented so far. Each time a new interval is presented, Algorithm inserts it into all maintained linear extensions and is not allowed to change the ordering of the previously introduced elements. Reading carefully the theorem of Rabinovitch on dimension of semi-orders one can prove that Algorithm needs only 3 linear extensions when Spoiler presents intervals of unit length. With the introduction of proper intervals, however, Algorithm can be forced to use one more extension. We prove that the value of the game on proper intervals is exactly 4.

rabinovitch.pdf (pdf, 238 KB )

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