Antonios Antoniadis

With the adoption of electric vehicles emerges a need for coordinated charging strategies to cater to the increased and often synchronized energy demand without violating physical infrastructure limits. Common charging strategies repeatedly solve a corresponding offline problem. In “Relating Electric Vehicle Charging to Speed Scaling with Job-Specific Speed Limits,” Winschermann, Antoniadis, Gerards, Hoogsteen, and Hurink thoroughly analyze that offline problem and present the flow-based offline charging scheduler (FOCS), an algorithm that solves the problem to optimality. The authors continue to quantify the approximation ratio of repeatedly solving the offline problem throughout the day as opposed to solving the offline problem with a priori knowledge of future arrivals. Numerical experiments confirmed that the found worst-case approximation ratio of 4 is far from the achieved empirical ratio of 1.3 when evaluating the ratio for real-world electric vehicle charging instances. Experiments based on that same real-world data show that FOCS only takes seconds to schedule 400 EVs in 15-minute granularity, which is competitive with commercial solvers.

We study online interval scheduling in the irrevocable setting, where each interval must be immediately accepted or rejected upon arrival. The objective is to maximize the total length of accepted intervals while ensuring that no two accepted intervals overlap. We consider this problem in a learning-augmented setting, where the algorithm has access to (machine-learned) predictions. The goal is to design algorithms that leverage these predictions to improve performance while maintaining robust guarantees in the presence of prediction errors. Our main contribution is the SemiTrust-and-Switch framework, which provides a unified approach for combining prediction-based and classical interval scheduling algorithms. This framework applies to both deterministic and randomized algorithms and captures the trade-off between consistency (performance under accurate predictions) and robustness (performance under adversarial inputs). Moreover, we provide lower bounds, proving the tightness of this framework in particular settings. We further design a randomized algorithm that smoothly interpolates between prediction-based and robust algorithms. This algorithm achieves both robustness and smoothness--its performance degrades gracefully with the quality of the prediction.

The design of microchips is a complex process, and is therefore naturally broken down to the design of many smaller components. The largest such components are referred to as `macros'. In these proceedings we investigate the problem of placing macros on a chip optimally, subject to distance and grid constraints. This problem was formulated by Synopsis. As the general problem is known to be NP-hard, we propose several algorithms with various heuristics.

Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision-making systems that are based on such predictors need not only benefit from good predictions, but should also achieve a decent performance when the predictions are inadequate. In this article, we propose a prediction setup for arbitrary metrical task systems (MTS) (e.g., caching , k -server, and convex body chasing ) and online matching on the line . We utilize results from the theory of online algorithms to show how to make the setup robust. Specifically, for caching, we present an algorithm whose performance, as a function of the prediction error, is exponentially better than what is achievable for general MTS. Finally, we present an empirical evaluation of our methods on real-world datasets, which suggests practicality.