On the Complexity of Speed Scaling

DOI10.1007/978-3-662-48054-0_7zbMath1465.68030OpenAlexW1788381686MaRDI QIDQ2946378

Peter Kling, Neal Barcelo, Michele Scquizzato, Michael Nugent, Kirk R. Pruhs

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: http://d-scholarship.pitt.edu/25280/1/Neal-Barcelo-Dissertation.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (5)

Optimizing resource speed for two-stage real-time tasks ⋮ Energy complexity of satisfying assignments in monotone circuits: on the complexity of computing the best case ⋮ Efficient computation of optimal energy and fractional weighted flow trade-off schedules ⋮ Optimal Speed Scaling with a Solar Cell ⋮ Models and algorithms for energy-efficient scheduling with immediate start of jobs

Cites Work

• Unnamed Item
• Unnamed Item
• Scheduling equal-length jobs on identical parallel machines
• Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times
• Speed Scaling with an Arbitrary Power Function
• Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules
• Scheduling for Speed Bounded Processors
• Speed Scaling Functions for Flow Time Scheduling Based on Active Job Count
• Speed Scaling for Weighted Flow Time
• Non-clairvoyant Speed Scaling for Weighted Flow Time
• Energy-efficient algorithms for flow time minimization
• Getting the best response for your erg
• Dual Techniques for Scheduling on a Machine with Varying Speed
• Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms

This page was built for publication: On the Complexity of Speed Scaling