On Online Labeling with Large Label Set

DOI10.1137/17M1117458zbMath1429.68333OpenAlexW2954903633MaRDI QIDQ5232147

Martin Babka, Michal Koucký, Vladimŕ Čunát, Jan Bulánek, Michael E. 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

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

Cites Work

• Unnamed Item
• New bounds for the controller problem
• Minimal on-line labelling
• A density control algorithm for doing insertions and deletions in a sequentially ordered file in a good worst-case time
• On Online Labeling with Polynomially Many Labels
• A locality-preserving cache-oblivious dynamic dictionary
• Tight Lower Bounds for the Online Labeling Problem
• Lower bounds for monotonic list labeling
• A Tight Lower Bound for Online Monotonic List Labeling
• On Randomized Online Labeling with Polynomially Many Labels
• Tight lower bounds for the online labeling problem
• Cache-Oblivious B-Trees

This page was built for publication: On Online Labeling with Large Label Set