11 citations · 26 across the 13 of their papers we have counts for
19 papers · 1 filter
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…
Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search
Ziyad Benomar, Lorenzo Croissant, Vianney Perchet +1
One-max search is a classic problem in online decision-making, in which a trader acts on a sequence of revealed prices and accepts one of them irrevocably to maximise its profit. T…
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…
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…
Competitive Search in the Line and the Star with Predictions
Spyros Angelopoulos
We study the classic problem of searching for a hidden target in the line and the -ray star, in a setting in which the searcher has some prediction on the hider's position. We f…
Rényi-Ulam Games and Online Computation with Imperfect Advice
Spyros Angelopoulos, Shahin Kamali
We study the nascent setting of online computation with imperfect advice, in which the online algorithm is enhanced by some prediction encoded in the form of a possibly erroneous b…
Online Search With Best-Price and Query-Based Predictions
Spyros Angelopoulos, Shahin Kamali, Dehou Zhang
In the online (time-series) search problem, a player is presented with a sequence of prices which are revealed in an online manner. In the standard definition of the problem, for e…
Competitive Sequencing with Noisy Advice
Spyros Angelopoulos, Diogo Arsénio, Shahin Kamali
Several well-studied online resource allocation problems can be formulated in terms of infinite, increasing sequences of positive values, in which each element is associated with a…
Online Bin Packing with Predictions
Spyros Angelopoulos, Shahin Kamali, Kimia Shadkami
Bin packing is a classic optimization problem with a wide range of applications, from load balancing to supply chain management. In this work, we study the online variant of the pr…
Online Search with Maximum Clearance
Spyros Angelopoulos, Malachi Voss
We study the setting in which a mobile agent must locate a hidden target in a bounded or unbounded environment, with no information about the hider's position. In particular, we co…
Online Search With a Hint
Spyros Angelopoulos
The linear search problem, informally known as the cow path problem, is one of the fundamental problems in search theory. In this problem, an immobile target is hidden at some unkn…
Online Computation with Untrusted Advice
Spyros Angelopoulos, Christoph Dürr, Shendan Jin +2
We study a generalization of the advice complexity model of online computation in which the advice is provided by an untrusted source. Our objective is to quantify the impact of un…
Interruptible Algorithms for Multiproblem Solving
Spyros Angelopoulos, Alejandro Lopez-Ortiz
In this paper we address the problem of designing an interruptible system in a setting in which problem instances, all equally important, must be solved concurrently. The syste…
Best-of-two-worlds analysis of online search
Spyros Angelopoulos, Christoph Dürr, Shendan Jin
In search problems, a mobile searcher seeks to locate a target that hides in some unknown position of the environment. Such problems are typically considered to be of an on-line na…
Online Maximum Matching with Recourse
Spyros Angelopoulos, Christoph Dürr, Shendan Jin
We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameter . An online algorithm for this problem has to maintain…
Optimal strategies for weighted ray search
Spyros Angelopoulos, Konstantinos Panagiotou
We introduce and study the general setting of weighted search in which a number of targets, each with a certain weight, are hidden in a star-like environment that consists of i…
Stochastic dominance and the bijective ratio of online algorithms
Spyros Angelopoulos, Marc P. Renault, Pascal Schweitzer
Stochastic dominance is a technique for evaluating the performance of online algorithms that provides an intuitive, yet powerful stochastic order between the compared algorithms. A…
Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems
Spyros Angelopoulos, Giorgio Lucarelli, Nguyen Kim Thang
We study online scheduling problems on a single processor that can be viewed as extensions of the well-studied problem of minimizing total weighted flow time. In particular, we pro…