On Online Labeling with Large Label Set

DOI10.1137/17M1117458zbMATH Open1429.68333OpenAlexW2954903633MaRDI QIDQ5232147FDOQ5232147

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

Cites Work

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

Cited In (5)

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

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)