Machine Covering in the Random-Order Model.

Abstract: In the Online Machine Covering problem, jobs, defined by their sizes, arrive one by one and have to be assigned to m parallel and identical machines, with the goal of maximizing the load of the least-loaded machine. Unfortunately, the classical model allows only fairly pessimistic performance guarantees: The best possible deterministic ratio of m is achieved by the Greedy-strategy, and the best known randomized algorithm has competitive ratio Õ(m^(1/2)), which cannot be improved by more than a logarithmic factor.

In this talk, we will discuss results for the Machine Covering problem in the random-order model. Here, no extra resources are present but, instead, the adversary is weakened in that it can only decide upon the input set while jobs are revealed uniformly at random. It is particularly relevant to Machine Covering where lower bounds usually come from highly structured input sequences.

We first analyze Graham’s Greedy-strategy in this context and show that its competitive ratio decreases slightly to O(m/log(m)), which is asymptotically tight. Then, we will present an improved Õ(m^(1/4))-competitive algorithm for the problem. This result is achieved by exploiting the extra information coming from the random order of the jobs, using sampling techniques to devise an improved mechanism to distinguish jobs that are relatively large from small ones. Time permitting, we will also present a lower bound, showing that no algorithm can have a competitive ratio of O(log(m)/loglog(m)) in the random-order model. This lower bound is achieved by studying a variant of the Secretary problem.