An $\mathcal{O}(\log {m})$-Competitive Algorithm for Online Machine Minimization

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

zbMATH Keywords

multiprocessor schedulingcompetitive analysisonline algorithms

Mathematics Subject Classification ID

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