The Online Labeling Problem

Abstract

Setříděné pole je zásadní algoritmický koncept, jehož online varianta je základem pro problém online labelingu. Problém online labelingu je definován následovně. Vstupem je pole velikosti m a posloupnost celých čísel z universa {1,...,r} v libovolném pořadí délky n. Naším úkolem je udržovat všechna přijatá čísla setříděná v poli. Mezi vloženými čísly mohou být mezery. Protože závěrečné pořadí čísel nelze určit, dokud nejsou vložena všechna, je povoleno čísla v poli přesouvat. Cílem je minimalizovat počet přesunů. Ukážeme dva algoritmy, které společně poskytují optimální řešení pro téměř všechny hodnoty m coby funkce n. Dokážeme těsné dolní odhady pro téměř všechny hodnoty m. Zavedeme notaci omezeného universa vstupní množiny čísel a dokážeme dolní odhady i pro tuto variantu. Dokážeme dolní odhady i pro případ randomizovaných algoritmů. Powered by TCPDF (www.tcpdf.org)

A sorted array is a fundamental algorithmic concept. Its on-line variant gives rise to the online labeling problem. In the online labeling problem we are given an array of size m and a stream of n integers from the universe {1, ..., r} coming in an arbitrary order. Our task is to maintain all received items in the array in sorted order. The inserted items do not have to be stored consecutively in the array. Since the final order of the items is not known until we see all the items, moves of already inserted items are allowed but should be minimized. We present two algorithms which together provide an optimal solution for almost all values of m as a function of n. We provide tight lower bounds for almost all ranges of m. We introduce a notion of the limited universe and prove lower bounds also in that setting. Some of our lower bounds also apply to randomized algorithms. Powered by TCPDF (www.tcpdf.org)