Name
Abstract | ||
|---|---|---|
This paper investigates the performance of online dynamic speed scaling algorithms for the objective of minimizing a linear combination of energy and response time. We prove that (SRPT, P--1 (n)), which uses Shortest Remaining Processing Time (SRPT) scheduling and processes at speed such that the power used is equal to the queue length, is 2-competitive for a very wide class of power-speed tradeoff functions. Further, we prove that there exist tradeoff functions such that no online algorithm can attain a competitive ratio less than 2. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1145/1639562.1639576 | SIGMETRICS Performance Evaluation Review |
Keywords | Field | DocType |
linear combination,response time,tradeoff function,competitive ratio,processing time,online algorithm,power-speed tradeoff function,optimal speed scaling,wide class,online dynamic speed,arbitrary power function,queue length,power function | Power function,Online algorithm,Linear combination,Mathematical optimization,Scheduling (computing),Computer science,Bipartite graph,Queue,Response time,Real-time computing,Distributed computing,Competitive analysis | Journal |
Volume | Issue | Citations |
37 | 2 | 26 |
PageRank | References | Authors |
1.41 | 16 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| L. L.H. Andrew | 1 | 918 | 52.52 |
| Adam Wierman | 2 | 1635 | 106.57 |
| Ao Tang | 3 | 254 | 18.74 |