Machine Covering in the Random-Order Model

Susanne Albers, Waldo Gálvez, Maximilian Janke

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 O~(m), which cannot be improved by more than a logarithmic factor. Modern results try to mitigate this by studying semi-online models, where additional information about the job sequence is revealed in advance or extra resources are provided to the online algorithm. In this work, we study the Machine Covering problem in the recently popular 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 are usually associated to highly structured input sequences. We first analyze Graham’s Greedy-strategy in this context and establish that its competitive ratio decreases slightly to Θ(mlog(m)), which is asymptotically tight. Then, as our main result, we present an improved O~(m4)-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. We complement this result with a first 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 novel variant of the Secretary problem, which could be of independent interest.

Original languageEnglish
Pages (from-to)1560-1585
Number of pages26
JournalAlgorithmica
Volume85
Issue number6
DOIs
StatePublished - Jun 2023

Keywords

  • Machine Covering
  • Online Algorithms
  • Random-Order
  • Scheduling

Fingerprint

Dive into the research topics of 'Machine Covering in the Random-Order Model'. Together they form a unique fingerprint.

Cite this