Energy-Efficient Computing
Final Report Abstract
The research project contributed to our knowledge in the area energy-efficient computing. A cornerstone algorithmic problem in the area is that of designing scheduling algorithms for processors equipped with a so-called sleep state, where the processor can reside in order to induce energy savings when there is no load to be processed. Although deadline-based scheduling on one such processor has been well understood for more than a decade, the same problem on multiple processors has proved quite challenging. As part of this research project, the first constant-approximation algorithm for the problem was developed, based on an elegant linear programming relaxation along with an intricate rounding technique. Since this particular scheduling problem appears as a special case within several other problems in the area, it seems likely that our approach can help in developing (improved) algorithms for them as well. A second major contribution of the project lies in exploring connections of speed-scaling and mechanism design. These are gaining in importance and relevance due to the increase in popularity of cloud computing. As part of the research project, we developed a mechanism for the service operator of such a cloud-computing service that decides on how each submitted task should be processed on a speed-scalable processor as well as the payment charged to each customer. This mechanism has several desirable properties: the induced game has a (mixed) Nash equilibrium and a constant Price of Anarchy, the sum of payments adds up to the total energy consumption, it is computationally tractable for both the operator and the customers, and the communication complexity is low. Building upon these results, we were able to extend them to more general settings including the online case, as well as the case in which there are multiple parallel cloud-computing servers. A third aspect of energy-efficient computing that was investigated is concerned with the problems of chasing convex functions and bodies, problems motivated from right-sizing of data centers in order to conserve energy. A tight lower bound for chasing 1-dimensional functions was developed, as well as the first polynomial-time approximation scheme (PTAS) for an offline variant of chasing convex bodies. Finally, we developed a specific setup within the very novel area of machine learning augmented online algogrithms. Although we were only able to demonstrate (both theoretically and practically) the performance of this setup on some more basic online problems, there are reasons to believe that this novel area in general, as well as our specific setup in particular are likely to be useful tools for designing energy-efficient algorithms as well.
Publications
- A Tight Lower Bound for Online Convex Optimization with Switching Costs. In Workshop on Approximation and Online Algorithms (WAOA’17), Lecture Notes in Computer Science, vol. 10787, pages 164–175, Springer, 2017
Antonios Antoniadis and Kevin Schewior
(See online at https://doi.org/10.1007/978-3-319-89441-6_13) - A Near Optimal Mechanism for Energy Aware Scheduling. In Symposium on Algorithmic Game Theory (SAGT’18), Lecture Notes in Computer Science, vol. 11059, pages 31–42, Springer, 2018
Antonios Antoniadis and Andrés Cristi
(See online at https://doi.org/10.1007/978-3-319-99660-8_4) - A General Framework for Energy-Efficient Cloud Computing Mechanisms. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS’20), pages 70–78, International Foundation for Autonomous Agents and Multiagent Systems, 2020
Antonios Antoniadis and Andrés Cristi, Tim Oosterwijk and Alkmini Sgouritsa
(See online at https://doi.org/10.48448/kk46-6090) - A PTAS for Euclidean TSP with Hyperplane Neighborhoods. ACM Transactions on Algorithms, vol. 16, numb. 3, pages 38:1 – 38:16, 2020
Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma and Kevin Schewior
(See online at https://doi.org/10.1145/3383466) - Online metric algorithms with untrusted predictions. In International Conference on Machine Learning (ICML’20), Proceedings of Machine Learning Research, vol. 119, pages 345–355, PMLR, 2020
Antonios Antoniadis, Christian Coester, Marek Eli´s, Adam Polak and Bertrand Simon
- Parallel Machine Scheduling to Minimize Energy Consumption. In ACM-SIAM Symposium on Discrete Algorithms (SODA’20), pages 2758–2769, SIAM, 2020
Antonios Antoniadis, Naveen Garg, Gunjan Kumar and Nikhil Kumar
(See online at https://doi.org/10.48550/arXiv.1909.13345)
