Tight Lower Bounds for the Online Labeling Problem

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

zbMATH Keywords

lower boundsonline labelingfile maintenance problem

Mathematics Subject Classification ID

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