An O( m)-competitive algorithm for online machine minimization
DOI10.1137/1.9781611974331.CH12zbMATH Open1410.68406OpenAlexW4243147939MaRDI QIDQ4575587FDOQ4575587
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
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
Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Deterministic scheduling theory in operations research (90B35)
Cited In (8)
- Title not available (Why is that?)
- Competitive design and analysis for machine-minimizing job scheduling problem
- Online in-time service problem with minimal server assignment
- Non-preemptive scheduling in a smart grid model and its implications on 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
- An improved algorithm for online machine minimization
- Handling Critical Jobs Online: Deadline Scheduling and Convex-Body Chasing
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)
