Before revision:  We develop two online randomized policies that achieve constant-factor guarantees close to the upper bounds we establish for the performance of any online policy.
After revision:  We develop two online randomized policies that achieve constant-factor guarantees close to the upper bound we establish for the performance of any online policy.