Scheduling in the random-order model

DOI10.4230/LIPICS.ICALP.2020.68MaRDI QIDQ6842504zbMATH OpenFDO

Authors Susanne Albers, Maximilian Janke

Publication date 18 March 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2020.68

zbMATH Keywords

competitive analysislower boundmakespan minimizationonline algorithmrandom-orderscheduling

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• O( rank) competitive ratio for the matroid secretary problem
• A Better Algorithm for an Ancient Scheduling Problem
• A better lower bound for on-line scheduling
• A Knapsack Secretary Problem with Applications
• A lower bound for randomized on-line multiprocessor scheduling
• A lower bound for randomized on-line scheduling algorithms
• A multiple-choice secretary algorithm with applications to online auctions
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• An efficient algorithm for bin stretching
• An On-Line Scheduling Heuristic with Better Worst-Case Ratio Than Graham’s List Scheduling
• Approximating the optimal algorithm for online scheduling problems via dynamic programming
• Better Bounds for Online Scheduling
• Bounds for Certain Multiprocessing Anomalies
• scientific article; zbMATH DE number 4130003 (Why is no real title available?)
• scientific article; zbMATH DE number 5764830 (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 Bounds for the Online Scheduling Problem
• List's worst-average-case or WAC ratio
• Matroid Secretary Problems
• Maximizing profit with convex costs in the random-order model
• On-line scheduling revisited
• Online and Random-order Load Balancing Simultaneously
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online bipartite matching with unknown distributions
• Online makespan scheduling with sublinear advice
• Online scheduling with bounded migration
• Primal beats dual on online packing LPs in the random-order model
• Semi on-line algorithms for the partition problem
• Semi-on-line multiprocessor scheduling with given total processing time

This page was built for publication: Scheduling in the random-order model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6842504)