An O( m)-competitive algorithm for online machine minimization

DOI10.1137/1.9781611974331.CH12MaRDI QIDQ4575587zbMATH OpenOpenAlexFDO

Authors Lin Chen, Nicole Megow, Kevin Schewior

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974331.ch12

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)

Recommendations

• An \(\mathcal O(\log m)\)-competitive algorithm for online machine minimization
• Competitive design and analysis for machine-minimizing job scheduling problem
• New upper and lower bounds for online scheduling with machine cost
• A better lower bound for on-line scheduling
• An optimal online algorithm for scheduling two machines with release times

Cited in

(9)

• scientific article; zbMATH DE number 7561425 (Why is no real title available?)
• Non-preemptive scheduling in a smart grid model and its implications on machine minimization
• An improved algorithm for online machine minimization
• A general framework for handling commitment in online throughput maximization
• A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack
• Competitive design and analysis for machine-minimizing job scheduling problem
• Handling critical jobs online: deadline scheduling and convex-body chasing
• Online in-time service problem with minimal server assignment
• An \(\mathcal O(\log m)\)-competitive algorithm for online machine minimization

This page was built for publication: An \(\mathcal{O}(\log m)\)-competitive algorithm for online machine minimization

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