First-Fit is linear on posets excluding two long incomparable chains

DOI10.1007/S11083-010-9184-YMaRDI QIDQ651432zbMATH OpenOpenAlexFDO

Authors Gwenaël Joret, Kevin G. Milans

Publication date 13 December 2011

Published in Order (Search for Journal in Brave)

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

zbMATH Keywords

column construction methodFirst-Fit algorithmforbidden subposeton-line chain partition

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Partial orders, general (06A06) Analysis of algorithms and problem complexity (68Q25)

Abstract: A poset is (r + s)-free if it does not contain two incomparable chains of size r and s, respectively. We prove that when r and s are at least 2, the First-Fit algorithm partitions every (r + s)-free poset P into at most 8(r-1)(s-1)w chains, where w is the width of P. This solves an open problem of Bosek, Krawczyk, and Szczypka (SIAM J. Discrete Math., 23(4):1992--1999, 2010).

Recommendations

• An improved bound for first-fit on posets without two long incomparable chains
• On-line dimension for posets excluding two long incomparable chains
• Linear discrepancy of chain products and posets with bounded degree
• Linear inequalities for enumerating chains in partially ordered sets
• On linear extensions of finite posets
• On a long cycle in the graph of all linear extensions of a poset consisting of two disjoint chains
• A Dichotomy Theorem for First-Fit Chain Partitions
• On First-Fit coloring of ladder-free posets
• scientific article; zbMATH DE number 5073478
• A correlational inequality for linear extensions of a poset

Cites work

• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 6469191 (Why is no real title available?)
• A note on first-fit coloring of interval graphs
• A subexponential upper bound for the on-line chain partitioning problem
• Coloring interval graphs with First-Fit
• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• Intransitive indifference with unequal indifference intervals
• Max-coloring and online coloring with bandwidths on interval graphs
• On some packing problem related to dynamic storage allocation
• On-line chain partitions of orders: a survey
• On-line dimension for posets excluding two long incomparable chains
• The Linearity of First-Fit Coloring of Interval Graphs

Cited in

(11)

• On-line dimension for posets excluding two long incomparable chains
• A subexponential upper bound for the on-line chain partitioning problem
• On First-Fit coloring of ladder-free posets
• An easy subexponential bound for online chain partitioning
• An extremal problem on crossing vectors.
• An improved bound for first-fit on posets without two long incomparable chains
• On-line partitioning of width \(w\) posets into \(w^{O(\log\log w)}\) chains
• Chain minors are FPT
• A Dichotomy Theorem for First-Fit Chain Partitions
• Forbidden structures for efficient first-fit chain partitioning (extended abstract)
• Dimension of posets with planar cover graphs excluding two long incomparable chains

This page was built for publication: First-Fit is linear on posets excluding two long incomparable chains

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