Lower bounds for randomized algorithms for online chain partitioning

DOI10.1016/J.IPL.2012.05.010zbMATH Open1248.68548OpenAlexW2056991307MaRDI QIDQ456079FDOQ456079

Authors Claire Mathieu, Olga Ohrimenko

Publication date 23 October 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2012.05.010

zbMATH Keywords

randomized algorithmsposetchain partitiononline chain partitioning

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Combinatorics in computer science (68R05) Randomized algorithms (68W20) Combinatorics of partially ordered sets (06A07)

Cites work

• scientific article; zbMATH DE number 3993569 (Why is no real title available?)
• A decomposition theorem for partially ordered sets
• An Effective Version of Dilworth's Theorem
• On-line chain partitions of orders

Cited in

(4)

• On-line chain partitioning of up-growing interval orders
• An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains
• Improved lower bound on the on-line chain partitioning of semi-orders with representation
• First-Fit Algorithm for the On-Line Chain Partitioning Problem

This page was built for publication: Lower bounds for randomized algorithms for online chain partitioning

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