On-line partitioning of width w posets into w^O( w) chains

DOI10.1016/J.EJC.2020.103202MaRDI QIDQ2225405zbMATH OpenOpenAlexFDO

Authors Bartłomiej Bosek, Tomasz Krawczyk

Publication date 8 February 2021

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.00270

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Online algorithms; streaming algorithms (68W27)

Abstract: An on-line chain partitioning algorithm receives the elements of a poset one at a time, and when an element is received, irrevocably assigns it to one of the chains. In this paper, we present an on-line algorithm that partitions posets of width $w$ into $w^{O(loglogw)}$ chains. This improves over previously best known algorithms using $w^{O(logw)}$ chains by Bosek and Krawczyk and by Bosek, Kierstead, Krawczyk, Matecki, and Smith. Our algorithm runs in $w^{O(sqrtw)}n$ time, where $w$ is the width and $n$ is the size of a presented poset.

Recommendations

• An easy subexponential bound for online chain partitioning
• On-line chain partitions of orders: a survey
• On-line chain partitioning of up-growing interval orders
• On-line dimension for posets excluding two long incomparable chains
• Variants of online chain partition problem of posets

Cites work

• A note on first-fit coloring of interval graphs
• A subexponential upper bound for the on-line chain partitioning problem
• An easy subexponential bound for online chain partitioning
• An Effective Version of Dilworth's Theorem
• An improved bound for first-fit on posets without two long incomparable chains
• Automata, Languages and Programming
• Coloring interval graphs with First-Fit
• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• First-fit coloring on interval graphs has performance ratio at least 5
• First-Fit is linear on posets excluding two long incomparable chains
• scientific article; zbMATH DE number 3993569 (Why is no real title available?)
• Intransitive indifference with unequal indifference intervals
• Note on Dilworth's Decomposition Theorem for Partially Ordered Sets
• On some packing problem related to dynamic storage allocation
• On-line chain partitions of orders
• On-line chain partitions of orders: a survey
• The Linearity of First-Fit Coloring of Interval Graphs
• The NP-completeness column: An ongoing guide

Cited in

(8)

• An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
• An easy subexponential bound for online chain partitioning
• On-line dimension for posets excluding two long incomparable chains
• Variants of online chain partition problem of posets
• scientific article; zbMATH DE number 5762570 (Why is no real title available?)
• Improved lower bound on the on-line chain partitioning of semi-orders with representation
• Improved lower bounds on the on-line chain partitioning of posets of bounded dimension
• (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE

This page was built for publication: On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2225405)