5 papers
The Pareto Frontier of Randomized Learning-Augmented Online Bidding
Mathis Degryse, Imrane Saakour, Christoph Dürr +1
Online bidding is a classical problem in online decision-making, with applications in resource allocation, hierarchical clustering, and the analysis of approximation algorithms. We…
Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms
Spyros Angelopoulos, Christoph Dürr, Georgii Melidi
We initiate the systematic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both dete…
Scenario-Based Robust Optimization of Tree Structures
Spyros Angelopoulos, Christoph Dürr, Alex Elenter +1
We initiate the study of tree structures in the context of scenario-based robust optimization. Specifically, we study Binary Search Trees (BSTs) and Huffman coding, two fundamental…
Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms
Spyros Angelopoulos, Christoph Dürr, Alex Elenter +1
The study of online algorithms with machine-learned predictions has gained considerable prominence in recent years. One of the common objectives in the design and analysis of such…
Contract Scheduling with Distributional and Multiple Advice
Spyros Angelopoulos, Marcin Bienkowski, Christoph Dürr +1
Contract scheduling is a widely studied framework for designing real-time systems with interruptible capabilities. Previous work has showed that a prediction on the interruption ti…