A subexponential upper bound for the on-line chain partitioning problem
type: Item
instance of: scholarly article
title: A subexponential upper bound for the on-line chain partitioning problem
zbMATH Open document ID: 1349.68324
author: Bartłomiej Bosek
author: Tomasz Krawczyk
published in: Combinatorica
publication date: 2016-05-03T00:00:00Z
review text: The online chain partitioning problem is a game between two players: Spoiler and Algorithm. In each round Spoiler introduces a new point to the poset and gives its relation to all existing points. Algorithm's task is to maintain a chain partition of the growing poset by incorporating the new point into one of the already existing chains or creating a new chain for the new point. Spoiler tries to build a poset to force Algorithm to use as many chains as possible, while Algorithm's task is to keep the number of chains as small as possible. Let \(\text{val}(w)\) denote the smallest number \(n\) for which Algorithm has a strategy that can partition any poset of width \(w\) into at most \(n\) chains. By Dilworth's theorem \(\text{val}(w)\) would be \(w\) if the game were played off-line. For the on-line game the best upper bound so far is \(\text{val}(w) \leq (5^w-1)/4\) by \textit{H. A. Kierstead} [Trans. Am. Math. Soc. 268, 63--77 (1981; Zbl 0485.03019)], the highest lower bound is \(\text{val}(w) \geq (2-o(1))\binom{w+1}{2}\) from the survey paper by \textit{B. Bosek} et al. [Order 29, No. 1, 49--73 (2012; Zbl 1259.06002)] which slightly improves E. Szemerédi's earlier lower bound of \(\binom{w+1}{2}\). The main result of the paper is that \(\text{val}(w) \leq w^{13 \log w}\). The proof is by first reducing the chain partition problem to a so-called regular game, where Spoiler introduces certain antichains rather than points. In Lemma~3.1 it is proved that if Algorithm has a strategy for using at most \(\text{reg}(w)\) colors for the on-line regular game of width \(w\), then \[ \text{val}(w) \leq \text{reg}(1)+ \dots + \text{reg}(w). \] Second, the authors give a recursive algorithm for the on-line regular game and prove the recursion \[ \text{reg}(w) \leq 32\left(1+\binom{w^3+1}{2} \right)(2w-1)w^5 \text{val}(w/2) \] in Lemma~3.2. Putting the two lemmas together yields the desired upper bound for \(\text{val}(w)\).
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 05C57
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 6576805
zbMATH Keywords: online algorithm
zbMATH Keywords: chain partitioning
zbMATH Keywords: partially ordered set
MaRDI profile type: Publication
full work available at URL: s00493-014-2908-7
OpenAlex ID: W2083080918
cites work: On-line chain partitioning of up-growing interval orders
cites work: On-line chain partitions of orders: a survey
cites work: First-Fit Coloring of Incomparability Graphs
cites work: First-Fit Algorithm for the On-Line Chain Partitioning Problem
cites work: On-line chain partitioning as a model for real-time scheduling
cites work: On some packing problem related to dynamic storage allocation
cites work: An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains
cites work: On-line chain partitions of orders
cites work: On-line chain partitions of up-growing semi-orders
cites work: First-Fit is linear on posets excluding two long incomparable chains
cites work: An Effective Version of Dilworth's Theorem
cites work: Q4722060
cites work: A theory of recursive dimension of ordered sets
cites work: On First-Fit coloring of ladder-free posets
cites work: Q3950561
cites work: Q4871756
DOI: 10.1007/S00493-014-2908-7
description: scientific article; zbMATH DE number 6576805