An $\mathcal{O}(\log {m})$-Competitive Algorithm for Online Machine Minimization
From MaRDI portal
Publication:4561244
DOI10.1137/17M116032XzbMath1409.68055arXiv1506.05721OpenAlexW2902014351MaRDI QIDQ4561244
Lin Chen, Kevin Schewior, Nicole Megow
Publication date: 5 December 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1506.05721
Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)
Related Items
Efficient algorithms for scheduling parallel jobs with interval constraints in clouds, Online machine minimization with lookahead, A competitive algorithm for throughput maximization on identical machines, An improved algorithm for online machine minimization, Optimally Handling Commitment Issues in Online Throughput Maximization
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Open problems in real-time scheduling
- Scheduling with a minimum number of machines
- An improved algorithm for online machine minimization
- Online bin packing with arbitrary release times
- Maximal Flow Through a Network
- Speed scaling to manage energy and temperature
- Two-Processor Scheduling with Start-Times and Deadlines
- Some simple scheduling algorithms
- Competitive Design and Analysis for Machine-Minimizing Job Scheduling Problem
- Nonmigratory Online Deadline Scheduling on Multiprocessors
- A Dynamic Programming Framework for Non-Preemptive Scheduling Problems on Multiple Machines [Extended Abstract]
- Optimal time-critical scheduling via resource augmentation