A greedy approximation algorithm for minimum-gap scheduling

DOI10.1007/S10951-016-0492-YMaRDI QIDQ2400437zbMATH OpenOpenAlexFDO

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

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

approximation algorithmsgreedy algorithmsscheduling

Mathematics Subject Classification ID

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

Recommendations

• A greedy approximation algorithm for minimum-gap scheduling
• Scheduling with gaps: new models and algorithms
• Scheduling with gaps: new models and algorithms
• Scheduling with a minimum number of machines
• Scheduling to minimize gaps and power consumption

Cites work

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

Cited in

(6)

• Scheduling with gaps: new models and algorithms
• A greedy algorithm for the solution of the classical NP-hard scheduling problem of minimizing the total delay
• Scheduling with gaps: new models and algorithms
• A greedy approximation algorithm for minimum-gap scheduling
• An O(n^3)-time algorithm for the min-gap unit-length job scheduling problem
• Greedy minimum-energy scheduling

This page was built for publication: A greedy approximation algorithm for minimum-gap scheduling

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