ﻻ يوجد ملخص باللغة العربية
We show tight bounds for online Hamming distance computation in the cell-probe model with word size w. The task is to output the Hamming distance between a fixed string of length n and the last n symbols of a stream. We give a lower bound of Omega((d/w)*log n) time on average per output, where d is the number of bits needed to represent an input symbol. We argue that this bound is tight within the model. The lower bound holds under randomisation and amortisation.
We give cell-probe bounds for the computation of edit distance, Hamming distance, convolution and longest common subsequence in a stream. In this model, a fixed string of $n$ symbols is given and one $delta$-bit symbol arrives at a time in a stream.
Vizings celebrated theorem asserts that any graph of maximum degree $Delta$ admits an edge coloring using at most $Delta+1$ colors. In contrast, Bar-Noy, Naor and Motwani showed over a quarter century that the trivial greedy algorithm, which uses $2D
We consider the following online optimization problem. We are given a graph $G$ and each vertex of the graph is assigned to one of $ell$ servers, where servers have capacity $k$ and we assume that the graph has $ell cdot k$ vertices. Initially, $G$ d
We consider the file maintenance problem (also called the online labeling problem) in which n integer items from the set {1,...,r} are to be stored in an array of size m >= n. The items are presented sequentially in an arbitrary order, and must be st
An assignment of colours to the vertices of a graph is stable if any two vertices of the same colour have identically coloured neighbourhoods. The goal of colour refinement is to find a stable colouring that uses a minimum number of colours. This is