Seminar: Energy-efficient Algorithms


Energy has become a scarce and expensive resource. This also holds true for many computing environments. Power dissipation is critical in portable devices, such as laptops and mobile phones, in which the capacity of a battery is limited. Furthermore, electricity costs impose a substantial strain on the budget of computing and data centers so that effective power management strategies are required. This seminar will study algorithmic techniques for energy savings. The following three topics will be covered.

  • Power-down mechanisms: If a system is idle for a certain time period, it can be transitioned into low-power stand-by or sleep states. The goal is to find state transition schedules minimizing the overall energy consumption.
  • Dynamic Speed Scaling: Many modern microprocessors can run at variable speed/frequency. High speed implies high performance but also high energy consumption. The goal is to utilize the full speed/frequency spectrum of a processor and to apply low speed levels whenever possible.
  • Networks: The goal is to solve various routing and data transmission problems, typically with the objective to minimize the total transmission energy.

The seminar talks can be presented in German or English, depending on the preference of the students.

Selected Literature

  1. S. Irani, S. K. Shukla and R. K. Gupta. Online strategies for dynamic power management in systems with multiple power-saving states. ACM Trans. Embedded Comput. Syst. 2(3): 325-346, 2003.
  2. J. Augustine, S. Irani, and C. Swamy. Optimal power-down strategies. SIAM J. Comput, 37(5): 1499-1516, 2008.
  3. P. Baptiste. Scheduling unit tasks to minimize the number of idle periods: A polynomial time algorithm for offline dynamic power management. Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms, 364-367, 2006.
  4. F. Yao, A. Demers and S. Shenker. A scheduling model for reduced CPU energy. Proc. 36th Annual Symposium on Foundations of Computer Science, 374-382, 1995.
  5. M. Li, F. F. Yao. An efficient algorithm for computing optimal discrete voltage schedules. MFCS 2005: 652-663.
  6. N. Bansal, D. P. Bunde, H., Kirk Pruhs. Average rate speed scaling. LATIN 2008: 240-251.
  7. N. Bansal, T. Kimbrel and K. Pruhs. Speed scaling to manage energy and temperature. J. ACM 54(1): 2007.
  8. S. Albers, F. Müller and S. Schmelzer. Speed scaling on parallel processors. Proc. 19th Annual ACM Symposium on Parallel Algorithms and Architectures, 289 - 298, 2007.
  9. K. Pruhs, P. Uthaisombut, G. Woeginger. Getting the best response for your erg. ACM Trans. Algorithms, 4(3), 2008: 1-17.
  10. N. Bansal, H. Chan, K. Pruhs. Speed scaling with an arbitrary power function. SODA 2009: 693-701.
  11. D. P. Bunde. Power-aware scheduling for makespan and flow. J. Scheduling 12(5): 489-500 (2009).
  12. S. Irani, S. Shukla and R. Gupta. Algorithms for power savings. ACM Transactions on Algorithms 3(4), 2007.
  13. S. Albers and A. Antoniadis: Race to idle: New algorithms for speed scaling with a sleep state. SODA 2012: 1266-1285
  14. L. Becchetti, P. Korteweg, A. Marchetti-Spaccamela, M. Skutella, L. Stougie and A. Vitaletti. Latency-Constrained Aggregation in Sensor Networks. ACM Transactions on Algorithms 6(1), 2009.
  15. M. Andrews, S. Antonakopoulos and L. Zhang. Minimum-cost network design with (dis)economies of scale. FOCS 2010: 585-592.

December 2017: Susanne Albers will give keynote address at the Graduation Day, Department of Computer Science at RWTH Aachen University.

ESA/ALGO 2019 will be organized by Susanne Albers and her group.

April 2017: New Research Training Center AdONE, funded by the German Research Foundation.

Susanne Albers receives ERC Advanced Grant. Press release of the Bavarian State Ministry of the Sciences, Research and the Arts.

August 2016: Susanne Albers is keynote speaker at Euro-Par 2016, Grenoble.

Susanne Albers, Nicole Megow and Andreas S. Schulz will organize MAPSP 2017.

Juni 2016: Susanne Albers gives an invited lecture at the Academy of Sciences and Literature, Mainz.

September 2015: Susanne Albers is invited speaker at MPI-INF – 25th Anniversary. The program features several Turing Award winners, Leibniz Prize winners, Humboldt Prize winners and ERC Grant winners.

June 2015: Susanne Albers is keynote speaker at the 31st International Symposium on Computational Geometry (SOCG15), Eindhoven.

June 2015: Susanne Albers is invited speaker of the tutorial on Network Creation Games: How Does the Internet Form? organized by Erik D. Demaine (MIT) and MohammadTaghi Hajiaghayi (University of Maryland). 16th Conference on Electronic Commerce (EC15), Portland, Oregon.

Lehrstuhl für Theoretische Informatik
Prof. Dr. Susanne Albers

Boltzmannstr. 3
85748 Garching bei München

Tel +89.289.17706
Fax +89.289.17707