A competitive algorithm for throughput maximization on identical machines

DOI10.1007/S10107-023-02045-0MaRDI QIDQ6589759zbMATH OpenFDO

Authors Benjamin Moseley, Kirk Pruhs, Clifford Stein, Rudy Zhou

Publication date 20 August 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10107-023-02045-0

zbMATH Keywords

competitive analysisonline algorithmscheduling

Mathematics Subject Classification ID

Approximation algorithms (68W25) Analysis of algorithms (68W40)

Cites work

• A competitive algorithm for throughput maximization on identical machines
• A general framework for handling commitment in online throughput maximization
• An O( m)-competitive algorithm for online machine minimization
• An improved algorithm for online machine minimization
• Eliminating migration in multi-processor scheduling
• Maximizing job completions online
• MOCA: A multiprocessor on-line competitive algorithm for real-time system scheduling
• On the competitiveness of on-line real-time task scheduling
• Optimal time-critical scheduling via resource augmentation
• Optimally Handling Commitment Issues in Online Throughput Maximization
• Speed is as powerful as clairvoyance

This page was built for publication: A competitive algorithm for throughput maximization on identical machines

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