Benjamin Doerr:

Vector Balancing Games with Aging

In this article we study an extension of the vector balancing game investigated by Spencer and Olson (which corresponds to the on-line version of the discrepancy problem for matrices). We assume that decisions in earlier rounds become less and less important as the game continues. For an aging parameter $q \ge 1$ we define the current move to be $q$ times more important than the previous one.

We consider two variants of this problem: First, the objective is a balanced partition at the end of the game, and second, it is to ensure a balanced partition throughout the game. We concentrate on the case $q \ge 2$. We give an optimal solution for the first problem and a nearly optimal one for the second.

Mathematics Subject Classification (1991): Primary 11K38; Secondary 90D05

Bibliographical note: Journal of Combinatorial Theory, Series A, 95 (2001), 219-233.

Keywords: vector balancing games, on-line algorithms, discrepancy

Mail an Jens Burmeister

[Thu Feb 19 18:56:35 2009]

Impressum