Dimension online of upgrowing

We analyze the adaptive coloring online problem for the upgrowing orders. We consider this problem as a two-person game. One person builds an order one point at a time. The other person responds by coloring the new point according to strictly determined rules. This problem is equivalent to certain variant of the dimension online prob-lem. The adaptive coloring problem can be also applied to the tasks scheduling online problem. Until now no non-trivial lower bound for these problems has been known. This paper contains a proof that for orders of width at most d any algorithm can be forced to use almost 2 · d colors- in other words the lower bound for adaptive coloring online problem of upgrowing orders of width at most d is almost 2 · d colors. Our considerations are motivated by the scheduling problem in a certain parallel environment. Tasks to be done are coming online but it is unknow