On-line Adaptive Chain Covering of Upgrowing Posets

1 Algorithmics Research Group
UJ - Jagiellonian University [Krakow]
Abstract : We analyze on-line chain partitioning problem and its variants as a two-person game. One person (Spoiler) builds an on-line poset presenting one point at time. The other one (Algorithm) assigns new point to a chain. Kierstead gave a strategy for Algorithm showing that width w posets can be on-line chain partitioned into $\frac{{5}^{w-1}}{4}$ chains. Felsner proved that if Spoiler presents an upgrowing poset, i.e., each new point is maximal at the moment of its arrival then there is a strategy for Algorithm using at most $\binom{w+1}{2}$ chains and it is best possible. An adaptive variant of this problem allows Algorithm to assign to the new point a set of chains and than to remove some of them (but not all) while covering next points. Felsner stated a hypothesis that in on-line adaptive chain covering of upgrowing posets Algorithm may use smaller number of chains than in non-adaptive version. In this paper we provide an argument suggesting that it is true. We present a class of upgrowing posets in which Spoiler has a strategy forcing Algorithm to use at least $\binom{w+1}{2}$ chains (in non-adaptive version) and Algorithm has a strategy using at most $O(w\sqrt{w})$ chains in adaptive version.
Keywords :
Type de document :
Communication dans un congrès
David, René and Gardy, Danièle and Lescanne, Pierre and Zaionc, Marek. Computational Logic and Applications, CLA '05, 2005, Chambéry, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05), pp.37-48, 2005, DMTCS Proceedings
Domaine :
Liste complète des métadonnées

Littérature citée [3 références]

https://hal.inria.fr/hal-01183337
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 11 août 2015 - 14:00:33
Dernière modification le : mercredi 10 mai 2017 - 17:40:19
Document(s) archivé(s) le : jeudi 12 novembre 2015 - 10:12:48

Fichier

dmAF0102.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

• HAL Id : hal-01183337, version 1

Citation

Bartłomiej Bosek, Piotr Micek. On-line Adaptive Chain Covering of Upgrowing Posets. David, René and Gardy, Danièle and Lescanne, Pierre and Zaionc, Marek. Computational Logic and Applications, CLA '05, 2005, Chambéry, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05), pp.37-48, 2005, DMTCS Proceedings. 〈hal-01183337〉

Métriques

Consultations de la notice

160

Téléchargements de fichiers