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 greater than or equal to 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 greater than or equal to 2. We give an optimal solution for the first problem and a nearly optimal one for the second. (C) 2001 Academic Press. [References: 11]
展开▼
