| Article ID: | iaor20173262 |
| Volume: | 79 |
| Issue: | 2 |
| Start Page Number: | 568 |
| End Page Number: | 597 |
| Publication Date: | Oct 2017 |
| Journal: | Algorithmica |
| Authors: | Antoniadis Antonios, Barcelo Neal, Consuegra Mario |
| Keywords: | energy, scheduling, combinatorial optimization, computers: information, programming: geometric |
We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade‐off schedule for a speed‐scalable processor with discrete speeds. Our algorithm uses a geometric approach that is based on structural properties obtained from a primal–dual formulation of the problem.