On-line Adaptive Chain Covering of Upgrowing Posets
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 c...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3473/pdf |
| _version_ | 1797270603136237568 |
|---|---|
| author | Bartłomiej Bosek Piotr Micek |
| author_facet | Bartłomiej Bosek Piotr Micek |
| author_sort | Bartłomiej Bosek |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:06:53Z |
| format | Article |
| id | doaj.art-136ff341b5e54000a94e1f7300e4dacc |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:06:53Z |
| publishDate | 2005-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-136ff341b5e54000a94e1f7300e4dacc2024-03-07T14:32:21ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502005-01-01DMTCS Proceedings vol. AF,...Proceedings10.46298/dmtcs.34733473On-line Adaptive Chain Covering of Upgrowing PosetsBartłomiej Bosek0Piotr Micek1Algorithmics Research GroupAlgorithmics Research GroupWe 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.https://dmtcs.episciences.org/3473/pdfposetorderon-line algorithmchain partition[info.info-lo] computer science [cs]/logic in computer science [cs.lo][info.info-sc] computer science [cs]/symbolic computation [cs.sc][info.info-hc] computer science [cs]/human-computer interaction [cs.hc] |
| spellingShingle | Bartłomiej Bosek Piotr Micek On-line Adaptive Chain Covering of Upgrowing Posets Discrete Mathematics & Theoretical Computer Science poset order on-line algorithm chain partition [info.info-lo] computer science [cs]/logic in computer science [cs.lo] [info.info-sc] computer science [cs]/symbolic computation [cs.sc] [info.info-hc] computer science [cs]/human-computer interaction [cs.hc] |
| title | On-line Adaptive Chain Covering of Upgrowing Posets |
| title_full | On-line Adaptive Chain Covering of Upgrowing Posets |
| title_fullStr | On-line Adaptive Chain Covering of Upgrowing Posets |
| title_full_unstemmed | On-line Adaptive Chain Covering of Upgrowing Posets |
| title_short | On-line Adaptive Chain Covering of Upgrowing Posets |
| title_sort | on line adaptive chain covering of upgrowing posets |
| topic | poset order on-line algorithm chain partition [info.info-lo] computer science [cs]/logic in computer science [cs.lo] [info.info-sc] computer science [cs]/symbolic computation [cs.sc] [info.info-hc] computer science [cs]/human-computer interaction [cs.hc] |
| url | https://dmtcs.episciences.org/3473/pdf |
| work_keys_str_mv | AT bartłomiejbosek onlineadaptivechaincoveringofupgrowingposets AT piotrmicek onlineadaptivechaincoveringofupgrowingposets |