A greedy approximation algorithm for minimum-gap scheduling

DOI10.1007/s10951-016-0492-yzbMath1376.90024OpenAlexW2477631381MaRDI QIDQ2400437

Fei Li, Uriel Feige, Sanjeev Khanna, Joseph (Seffi) Naor, Mohammad Taghi Hajiaghayi, Marek Chrobak

Publication date: 1 September 2017

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-016-0492-y

zbMATH Keywords

schedulingapproximation algorithmsgreedy algorithms

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

An \(O(n^3)\)-time algorithm for the min-gap unit-length job scheduling problem ⋮ Scheduling with gaps: new models and algorithms

Cites Work

• On the NP-hardness of speed scaling with sleep state
• On single-machine scheduling without intermediate delays
• Scheduling to minimize gaps and power consumption
• Polynomial-time algorithms for minimum energy scheduling
• Polynomial Time Algorithms for Minimum Energy Scheduling
• Scheduling unit tasks to minimize the number of idle periods
• Race to idle