First-Fit is linear on posets excluding two long incomparable chains
From MaRDI portal
Publication:651432
DOI10.1007/S11083-010-9184-YzbMATH Open1232.06003arXiv1006.5704OpenAlexW3099995778MaRDI QIDQ651432FDOQ651432
Kevin G. Milans, Gwenaël Joret
Publication date: 13 December 2011
Published in: Order (Search for Journal in Brave)
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).
Full work available at URL: https://arxiv.org/abs/1006.5704
Online algorithms; streaming algorithms (68W27) Partial orders, general (06A06) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Intransitive indifference with unequal indifference intervals
- A subexponential upper bound for the on-line chain partitioning problem
- First-Fit Algorithm for the On-Line Chain Partitioning Problem
- On some packing problem related to dynamic storage allocation
- On-line chain partitions of orders: a survey
- Coloring interval graphs with First-Fit
- The Linearity of First-Fit Coloring of Interval Graphs
- On-line dimension for posets excluding two long incomparable chains
- Max-coloring and online coloring with bandwidths on interval graphs
- A note on first-fit coloring of interval graphs
Cited In (8)
- A subexponential upper bound for the on-line chain partitioning problem
- 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
- Forbidden structures for efficient first-fit chain partitioning (extended abstract)
- Dimension of posets with planar cover graphs excluding two long incomparable chains
- On-line dimension for posets excluding two long incomparable chains
Recommendations
- Title not available (Why is that?) 👍 👎
- An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains 👍 👎
- On First-Fit coloring of ladder-free posets 👍 👎
- On-line dimension for posets excluding two long incomparable chains 👍 👎
- Linear discrepancy of chain products and posets with bounded degree 👍 👎
- On linear extensions of finite posets 👍 👎
- A correlational inequality for linear extensions of a poset 👍 👎
- On a long cycle in the graph of all linear extensions of a poset consisting of two disjoint chains 👍 👎
- Linear inequalities for enumerating chains in partially ordered sets 👍 👎
- A Dichotomy Theorem for First-Fit Chain Partitions 👍 👎
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)
