** Reference:**
* APPROX 2001*, LNCS 2129, pages 75-89. Springer-Verlag, 2001.

** Abstract: **
We introduce the notion of *incremental* codes. Unlike a regular
code of a given rate, which is an unordered set of elements with a
large minimum distance, an incremental code is an ordered vector of
elements each of whose prefixes is a good regular code (of the
corresponding rate). Additionally, while the quality of a regular
code is measured by its minimum distance, we measure the quality of an
incremental code *C* by its *competitive ratio*, *A*:
the minimum distance of each prefix of *C* has to be at most
a factor of *A* smaller than the minimum distance of the best
regular code of the same rate.

We first consider incremental codes over an arbitrary compact metric
space *M*, and construct a 2-competitive code for *M*.
When *M* is finite, the construction takes time *O(|M|^2)*,
exhausts the entire space, and is NP-hard to improve in general.
We then concentrate on two specific spaces: the real interval [0,1]
and, most importantly, the Hamming space *F^n*. For the interval
[0,1] we construct an optimal (infinite) code of competitive ratio
*ln(4) ~ 1.386*.
For the Hamming space *F^n* (where the generic 2-competitive
constructive is not efficient), we show the following. If *|F| >= n*,
we construct optimal (and efficient) 1-competitive code that exhausts
*F^n* (has rate 1). For small alphabets (*|F|* < *n*),
we show that 1-competitive codes do not exist and provide several efficient
constructions of codes achieving constant competitive ratios. In
particular, our best construction has rate *(1-o(1))* and competitive
ratio *(2+o(1))*, essentially matching the bounds in the generic
construction.

** Keywords: **
Codes, Competetive ratio.

** Availability: **
Paper available as Compressed PostScript
(113 Kbyte).

Shai Halevi's home page.