Improved randomized online scheduling of intervals and jobs
From MaRDI portal
Publication:2254495
DOI10.1007/s00224-013-9528-2zbMath1319.68257arXiv1204.2933MaRDI QIDQ2254495
Stanley P. Y. Fung, Chung Keung Poon, Feifeng Zheng
Publication date: 5 February 2015
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1204.2933
online algorithms; lower bound; randomized algorithms; interval and job scheduling; preemption with restarts
90B35: Deterministic scheduling theory in operations research
68W20: Randomized algorithms
68W27: Online algorithms; streaming algorithms
Related Items
Online scheduling of jobs with fixed start times on related machines, Online C-benevolent job scheduling on multiple machines, Competitive analysis of online machine rental and online parallel machine scheduling problems with workload fence, Primal-dual analysis for online interval scheduling problems, Online interval scheduling to maximize total satisfaction, Online interval scheduling on two related machines: the power of lookahead
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Improved on-line broadcast scheduling with deadlines
- A near optimal scheduler for on-demand data broadcasts
- Improved randomized results for the interval selection problem
- Online interval scheduling: Randomized and multiprocessor cases
- On the competitiveness of on-line real-time task scheduling
- Randomized online interval scheduling
- A short proof that `proper = unit'
- On-line scheduling of jobs with fixed start and end times
- Online scheduling with partial job values: does timesharing or randomization help?
- Scheduling broadcasts with deadlines
- Online competitive algorithms for maximizing weighted throughput of unit jobs
- An improved randomized on-line algorithm for a weighted interval selection problem
- On randomized online scheduling
- Improved Randomized Online Scheduling of Unit Length Intervals and Jobs
- Bounding the Power of Preemption in Randomized Scheduling
- $\text{D}^{\textit{over}}$: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems
- Online Scheduling of Equal‐Length Jobs: Randomization and Restarts Help
