In: Order Online First Pages 1-23 Springer Netherlands 2012.
Abstract
We analyze the on-line dimension of partially ordered sets as a value of a two-person game between Algorithm and Spoiler. The game is played in rounds. Spoiler presents an on-line order of width at most w, one point at a time. Algorithm maintains its realizer, i.e., the set of d linear extensions which intersect to the presented order. Algorithm may not change the ordering of the previously introduced elements in the existing linear extensions. The value of the game val(w) is the least d such that Algorithm has a strategy against Spoiler presenting any order of width at most w. For interval orders Hopkins showed that val(w) <= 4w-4. We analyze the on-line dimension of semi-orders i.e., interval orders admitting a unit-length representation. For up-growing semi-orders of width w we prove a matching lower and upper bound of w. In the general (not necessarily up-growing) case we provide an upper bound of 2w.
@article{pub6563,
author = {
Bosek, Bartlomiej
and
Kloch, Kamil
and
Krawczyk, Tomasz
and
Micek, Piotr
},
title = {On-Line dimension of semi-orders},
year = {2012},
volume = {Online First},
pages = {1--23},
journal = {Order},
publisher = {Springer Netherlands}
}
German Research Center for Artificial Intelligence Deutsches Forschungszentrum für Künstliche Intelligenz
