An improved bound for first-fit on posets without two long incomparable chains

DOI10.1137/110855806zbMATH Open1282.06005arXiv1111.2370OpenAlexW3101306282MaRDI QIDQ4899045FDOQ4899045

David R. Wood, Vida Dujmović, Gwenaël Joret

Publication date: 4 January 2013

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: It is known that the First-Fit algorithm for partitioning a poset P into chains uses relatively few chains when P does not have two incomparable chains each of size k. In particular, if P has width w then Bosek, Krawczyk, and Szczypka (SIAM J. Discrete Math., 23(4):1992--1999, 2010) proved an upper bound of ckw^{2} on the number of chains used by First-Fit for some constant c, while Joret and Milans (Order, 28(3):455--464, 2011) gave one of ck^{2}w. In this paper we prove an upper bound of the form ckw. This is best possible up to the value of c.

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

Recommendations

• First-Fit is linear on posets excluding two long incomparable chains
• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• Forbidden structures for efficient first-fit chain partitioning (extended abstract)
• On-line dimension for posets excluding two long incomparable chains
• On First-Fit coloring of ladder-free posets

zbMATH Keywords

on-line chain partitionFirst-Fit

Mathematics Subject Classification ID

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

Cited In (8)

• Grundy Distinguishes Treewidth from Pathwidth
• A subexponential upper bound for the on-line chain partitioning problem
• First-Fit is linear on posets excluding two long incomparable chains
• An easy subexponential bound for online chain partitioning
• An extremal problem on crossing vectors.
• On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
• A Dichotomy Theorem for First-Fit Chain Partitions
• Dimension of posets with planar cover graphs excluding two long incomparable chains

This page was built for publication: An improved bound for first-fit on posets without two long incomparable chains

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