On online labeling with large label set

DOI10.1137/17M1117458MaRDI QIDQ5232147zbMATHOpenAlexFDO

Authors Martin Babka, Jan Bulánek, Vladimŕ Čunát, Michal Koucký, Michael Saks

Publication date 29 August 2019

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

Full work available at URL https://doi.org/10.1137/17m1117458

zbMATH Keywords

online algorithmslower boundsonline labelingfile maintenance problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On Online Labeling with Polynomially Many Labels
• Online labeling: algorithms, lower bounds and open questions
• Tight lower bounds for the online labeling problem
• Tight lower bounds for the online labeling problem
• On randomized online labeling with polynomially many labels

Cites work

• scientific article; zbMATH DE number 2119642 (Why is no real title available?)
• A Tight Lower Bound for Online Monotonic List Labeling
• A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time
• A locality-preserving cache-oblivious dynamic dictionary
• Cache-Oblivious B-Trees
• Lower bounds for monotonic list labeling
• Minimal on-line labelling
• New bounds for the controller problem
• On Online Labeling with Polynomially Many Labels
• On randomized online labeling with polynomially many labels
• Tight lower bounds for the online labeling problem
• Tight lower bounds for the online labeling problem

Cited in

(8)

• Online labeling: algorithms, lower bounds and open questions
• A tight lower bound for on-line monotonic list labeling
• A Tight Lower Bound for Online Monotonic List Labeling
• On randomized online labeling with polynomially many labels
• Minimal on-line labelling
• Tight lower bounds for the online labeling problem
• Tight lower bounds for the online labeling problem
• On Online Labeling with Polynomially Many Labels

This page was built for publication: On online labeling with large label set

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