Machine covering in the random-order model
From MaRDI portal
Abstract: In the Online Machine Covering problem jobs, defined by their sizes, arrive one by one and have to be assigned to parallel and identical machines, with the goal of maximizing the load of the least-loaded machine. 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 which is asymptotically tight. Then, as our main result, we present an improved -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 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.
Cites work
- A Better Algorithm for an Ancient Scheduling Problem
- A better lower bound for on-line scheduling
- A Knapsack Secretary Problem with Applications
- A multiple-choice secretary algorithm with applications to online auctions
- A polynomial-time approximation scheme for maximizing the minimum machine completion time
- A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
- A survey on makespan minimization in semi-online environments
- Algorithms with Predictions
- An approximation algorithm for max-min fair allocation of indivisible goods
- An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
- Analysis of Greedy Solutions for a Replacement Part Sequencing Problem
- Approximation and Online Algorithms
- Best fit bin packing with random order revisited
- Better Bounds for Online Scheduling
- Bounds for Certain Multiprocessing Anomalies
- Dynamic Programming and Decision Theory
- scientific article; zbMATH DE number 1670659 (Why is no real title available?)
- scientific article; zbMATH DE number 4130003 (Why is no real title available?)
- scientific article; zbMATH DE number 871933 (Why is no real title available?)
- scientific article; zbMATH DE number 1445351 (Why is no real title available?)
- scientific article; zbMATH DE number 3383344 (Why is no real title available?)
- Improved online algorithms for knapsack and GAP in the random order model
- Inequalities on the Lambert W function and hyperpower function
- List's worst-average-case or WAC ratio
- Matroid Secretary Problems
- Max-min online allocations with a reordering buffer
- Maximizing profit with convex costs in the random-order model
- New algorithms for an ancient scheduling problem.
- On-line machine covering
- Online and Random-order Load Balancing Simultaneously
- Online appointment scheduling in the random order model
- Online Scheduling via Learned Weights
- Online scheduling with bounded migration
- Primal beats dual on online packing LPs in the random-order model
- Random-Order Models
- Robust polynomial-time approximation schemes for parallel machine scheduling with job arrivals and departures
- Symmetry Exploitation for Online Machine Covering with Bounded Migration
- The Santa Claus problem
Cited in
(3)
This page was built for publication: Machine covering in the random-order model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6103518)
