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

2018/09/29 by Bartłomiej Bosek, Bosek, Bartłomiej, Tomasz Krawczyk +1
Computer Science · Mathematics · #68W27 #Advanced Combinatorial Mathematics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1810.00270

openalex publication_date 2018/09/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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(√(w))n time, where w is the width and n is the size of a presented poset.

Related

• Improved lower bounds on the on-line chain partitioning of posets of bounded dimension
• An easy subexponential bound for online chain partitioning
• Improved lower bound on the on-line chain partitioning of semi-orders with representation
• A Dichotomy Theorem for First-Fit Chain Partitions
• Lazy Queue Layouts of Posets