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

DOI10.1007/s11083-010-9184-yzbMath1232.06003arXiv1006.5704OpenAlexW3099995778MaRDI QIDQ651432

Kevin G. Milans, Gwenaël Joret

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

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

Related Items (8)

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

Cites Work

• Unnamed Item
• Unnamed Item
• A subexponential upper bound for the on-line chain partitioning problem
• On-line chain partitions of orders: a survey
• A note on first-fit coloring of interval graphs
• Coloring interval graphs with First-Fit
• On-line dimension for posets excluding two long incomparable chains
• Intransitive indifference with unequal indifference intervals
• First-Fit Algorithm for the On-Line Chain Partitioning Problem
• Max-coloring and online coloring with bandwidths on interval graphs
• The Linearity of First-Fit Coloring of Interval Graphs
• On some packing problem related to dynamic storage allocation

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