On-line chain partitions of orders: a survey
type: Item
instance of: scholarly article
title: On-line chain partitions of orders: a survey
zbMATH Open document ID: 1259.06002
author: Bartłomiej Bosek
author: Stefan Felsner
author: Kamil Kloch
author: Tomasz Krawczyk
author: Grzegorz Matecki
author: Piotr Micek
published in: Order
publication date: 2012-03-23T00:00:00Z
review text: The paper surveys the state of the art in the field of online-chain partitioning of partially ordered sets (posets) and contributes some new results. Online-chain partitioning may be described as a two-player game between Spoiler and Algorithm on a poset \(P\) as follows: Each round starts with Spoiler presenting an element \(p\) of \(P\) together with all its relations to already presented elements, i.e., the presented elements together form an induced subposet \(P'\) of \(P\). Afterwards, Algorithm has to assign \(p\) to a chain \(C_p\) of \(P'\) such that, together with the earlier assignments, \(C_p\) forms a chain-partition of \(P'\), i.e., \(\{C_q\mid q\in P'\}\) is a partition of \(P'\) into chains. The assignments made by Algorithm are irrevocable during the course of the game. It is Algorithm's goal to use as few chains as possible, while Spoiler wants to force many chains. Since the width \(w(P)\) is the minimum size of a chain-partition of \(P\) (in the offline setting) the value of the game is taken with respect to the class of width-\(w\) posets, i.e., \(\operatorname{val}(w)\) is the minimum size of a chain-partition that Algorithm can guarantee on this class. The paper describes a variety of classical and recent results and variations of the problem. The most important parts are: A sketch of the proof by Bosek and Krawczyk for the new sub-exponential bound \(\operatorname{val}(w)\leq w^{16\text{lg}w}\); a new lower bound \(\operatorname{val}(w)\geq (2-o(1)) {w+1\choose 2}\); the inclusion of some simplified proofs of previously published results; a comprehensive account on variants of the problem for interval orders; and a new lower bound for 2-dimensional up-growing orders.
reviewed by: Kolja Knauer
Mathematics Subject Classification ID: 06A07
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 91A05
Mathematics Subject Classification ID: 91A80
zbMATH DE Number: 6018080
zbMATH Keywords: survey paper
zbMATH Keywords: online-chain partitioning
zbMATH Keywords: partially ordered sets
MaRDI profile type: Publication
full work available at URL: s11083-011-9197-1
OpenAlex ID: W2151140709
Wikidata QID: Q72990570
cites work: Efficient dependency tracking for relevant events in concurrent systems
cites work: On-line chain partitioning of up-growing interval orders
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: Partially Ordered Sets
cites work: On-line chain partitions of orders
cites work: On-line chain partitions of up-growing semi-orders
cites work: Intransitive indifference with unequal indifference intervals
cites work: On-line and first fit colorings of graphs
cites work: An Effective Version of Dilworth's Theorem
cites work: Q4722060
cites work: The Linearity of First-Fit Coloring of Interval Graphs
cites work: A theory of recursive dimension of ordered sets
cites work: On-Line Coloring and Recursive Graph Theory
cites work: Coloring interval graphs with First-Fit
cites work: Q3950561
cites work: Q4918387
cites work: A note on first-fit coloring of interval graphs
cites work: Automata, Languages and Programming
cites work: Q5588432
cites work: Foundational aspects of theories of measurement
cites work: Optimal on-line coloring of circular arc graphs
cites work: Q4004146
cites work: Q4871756
DBLP publication ID: journals/order/BosekFKKMM12
DOI: 10.1007/S11083-011-9197-1
description: scientific article; zbMATH DE number 6018080