Tight Lower Bounds for the Online Labeling Problem
From MaRDI portal
Publication:3457193
DOI10.1137/130907653zbMath1333.68096arXiv1112.5636OpenAlexW2185212870MaRDI QIDQ3457193
Michal Koucký, Jan Bulánek, Michael E. Saks
Publication date: 11 December 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1112.5636
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Information storage and retrieval of data (68P20) Online algorithms; streaming algorithms (68W27)
Related Items (4)
Fragile complexity of adaptive algorithms ⋮ Fragile complexity of adaptive algorithms ⋮ On Online Labeling with Large Label Set ⋮ The Online House Numbering Problem: Min-Max Online List Labeling
Cites Work
- Unnamed Item
- 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
- Local management of a global resource in a communication network
- Lower bounds for monotonic list labeling
- A Tight Lower Bound for Online Monotonic List Labeling
- On Randomized Online Labeling with Polynomially Many Labels
- Controller and estimator for dynamic networks
- Cache-Oblivious B-Trees
This page was built for publication: Tight Lower Bounds for the Online Labeling Problem