An ℴ(log m)-Competitive Algorithm for Online Machine Minimization

DOI10.1137/1.9781611974331.ch12zbMath1410.68406OpenAlexW4243147939MaRDI QIDQ4575587

Kevin Schewior, Lin Chen, Nicole Megow

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

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

Related Items (7)

A parameterized complexity view on non-preemptively scheduling interval-constrained jobs: few machines, small looseness, and small slack ⋮ An improved algorithm for online machine minimization ⋮ Non-preemptive scheduling in a smart grid model and its implications on machine minimization ⋮ Online in-time service problem with minimal server assignment ⋮ Unnamed Item ⋮ Handling Critical Jobs Online: Deadline Scheduling and Convex-Body Chasing ⋮ A general framework for handling commitment in online throughput maximization

This page was built for publication: An ℴ(log m)-Competitive Algorithm for Online Machine Minimization