Spyros Angelopoulos

NeurIPS Conference 2025 Conference Paper

Learning-Augmented Online Bidding in Stochastic Settings

• Spyros Angelopoulos
• Bertrand Simon

Online bidding is a classic optimization problem, with several applications in online decision-making, the design of interruptible systems, and the analysis of approximation algorithms. In this work, we study online bidding under learning-augmented settings that incorporate stochasticity, in either the prediction oracle or the algorithm itself. In the first part, we study bidding under distributional predictions, and find Pareto-optimal algorithms that offer the best-possible tradeoff between the consistency and the robustness of the algorithm. In the second part, we study the power and limitations of randomized bidding algorithms, by presenting upper and lower bounds on the consistency/robustness tradeoffs. Previous works focused predominantly on oracles that do not leverage stochastic information on the quality of the prediction, and deterministic algorithms.

AAAI Conference 2025 Conference Paper

Scenario-Based Robust Optimization of Tree Structures

• Spyros Angelopoulos
• Christoph Dürr
• Alex Elenter
• Georgii Melidi

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 techniques for efficiently managing and encoding data based on a known set of frequencies of keys. Given a number of distinct scenarios, each defined by a frequency distribution over the keys, our objective is to compute a single tree of best-possible performance, relative to any scenario. We consider, as performance metrics, the competitive ratio, which compares multiplicatively the cost of the solution to the tree of least cost among all scenarios, as well as the regret, which induces a similar, but additive comparison. For BSTs, we show that the problem is NP-hard across both metrics. We also obtain an optimal competitive ratio that is logarithmic in the number of scenarios. For Huffman Trees, we likewise prove NP-hardness, and we present an algorithm with logarithmic regret, which we prove to be near-optimal by showing a corresponding lower bound. Last, we give a polynomial-time algorithm for computing Pareto-optimal BSTs with respect to their regret, assuming scenarios defined by uniform distributions over the keys. This setting captures, in particular, the first study of fairness in the context of data structures. We provide an experimental evaluation of all algorithms. To this end, we also provide mixed integer linear program formulation for computing optimal trees.

IJCAI Conference 2024 Conference Paper

Contract Scheduling with Distributional and Multiple Advice

• Spyros Angelopoulos
• Marcin Bienkowski
• Christoph Dürr
• Bertrand Simon

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 time can help improve the performance of contract-based systems, however it has relied on a single prediction that is provided by a deterministic oracle. In this work, we introduce and study more general and realistic learning-augmented settings in which the prediction is in the form of a probability distribution, or it is given as a set of multiple possible interruption times. For both prediction settings, we design and analyze schedules which perform optimally if the prediction is accurate, while simultaneously guaranteeing the best worst-case performance if the prediction is adversarial. We also provide evidence that the resulting system is robust to prediction errors in the distributional setting. Last, we present an experimental evaluation that confirms the theoretical findings, and illustrates the performance improvements that can be attained in practice.

NeurIPS Conference 2024 Conference Paper

Overcoming Brittleness in Pareto-Optimal Learning Augmented Algorithms

• Alex Elenter
• Spyros Angelopoulos
• Christoph Dürr
• Yanni Lefki

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 algorithms is to attain (Pareto) optimal tradeoffs between the {\em consistency} of the algorithm, i. e. , its performance assuming perfect predictions, and its {\em robustness}, i. e. , the performance of the algorithm under adversarial predictions. In this work, we demonstrate that this optimization criterion can be extremely brittle, in that the performance of Pareto-optimal algorithms may degrade dramatically even in the presence of imperceptive prediction error. To remedy this drawback, we propose a new framework in which the smoothness in the performance of the algorithm is enforced by means of a {\em user-specified profile}. This allows us to regulate the performance of the algorithm as a function of the prediction error, while simultaneouslymaintaining the analytical notion of consistency/robustness tradeoffs, adapted to the profile setting. We apply this new approach to a well-studied online problem, namely the {\em one-way trading} problem. For this problem, we further address another limitation of the state-of-the-art Pareto-optimal algorithms, namely the fact that they are tailored to worst-case, and extremely pessimistic inputs. We propose a new Pareto-optimal algorithm that leverages any deviation from the worst-case input to its benefit, and introduce a new metric that allows us to compare any two Pareto-optimal algorithms via a {\em dominance} relation.

TCS Journal 2024 Journal Article

Preface to special issue on theory and applications of Graph Searching

• Spyros Angelopoulos
• Pierre Fraigniaud
• Nicolas Nisse
• Dimitrios M. Thilikos

JAIR Journal 2023 Journal Article

Contract Scheduling with Predictions

• Spyros Angelopoulos
• Shahin Kamali

Contract scheduling is a general technique that allows the design of systems with interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous work on this topic has assumed that the interruption is a worst-case deadline that is unknown to the scheduler. In this work, we study new settings in which the scheduler has access to some imperfect prediction in regards to the interruption. In the first setting, which is inspired by recent advances in learning-enhanced algorithms, the prediction describes the time that the interruption occurs. The second setting introduces a new model in which predictions are elicited as responses to a number of binary queries. For both settings, we investigate trade-offs between the robustness (i.e., the worst-case performance of the schedule if the prediction is generated adversarially) and the consistency (i.e., the performance assuming that the prediction is error-free). We also establish results on the performance of the schedules as a function of the prediction error.

JAIR Journal 2023 Journal Article

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 problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. The online algorithm is enhanced with a potentially erroneous prediction concerning the frequency of item sizes in the sequence. We design and analyze online algorithms with efficient tradeoffs between the consistency, which is the competitive ratio assuming no prediction error, and the robustness, which is the competitive ratio under adversarial error. Moreover, we demonstrate that the performance of our algorithm degrades near-optimally as a function of the prediction error. This is the first theoretical and experimental study of online bin packing under competitive analysis in the realistic setting of learnable predictions. Previous work addressed only extreme cases with respect to the prediction error and relied on overly powerful and error-free oracles.

I&C Journal 2023 Journal Article

Online search with a hint

• Spyros Angelopoulos

We introduce the study of search problems, in a setting in which the searcher has some information, or hint concerning the hiding target. In particular, we focus on one of the fundamental problems in search theory, namely the linear search problem. Here, an immobile target is hidden at some unknown position on an unbounded line, and a mobile searcher, initially positioned at some specific point of the line called the root, must traverse the line so as to locate the target. The objective is to minimize the worst-case ratio of the distance traversed by the searcher to the distance of the target from the root, which is known as the competitive ratio of the search. We consider three settings in regards to the nature of the hint: i) the hint suggests the exact position of the target on the line; ii) the hint suggests the direction of the optimal search (i. e. , to the left or the right of the root); and iii) the hint is a general k-bit string that encodes some information concerning the target. Our objective is to study the Pareto-efficiency of strategies in this model, with respect to the tradeoff between consistency and robustness. Namely, we seek optimal, or near-optimal tradeoffs between the searcher's performance if the hint is correct (i. e. , provided by a trusted source) and if the hint is incorrect (i. e. , provided by an adversary). We prove several results in each of these three settings. For positional hints, we show that the optimal consistency of r-robust strategies is ( b r + 1 ) / ( b r − 1 ), where b r is defined to be equal to ρ r + ρ r 2 − 4 ρ r 2, and ρ r = ( r − 1 ) / 2, for all r ≥ 9. For directional hints, we show that for every b ≥ 1 and δ ∈ ( 0, 1 ], there exists a strategy with consistency equal to c = 1 + 2 ( b 2 b 2 − 1 + δ b 3 b 2 − 1 ) and robustness equal to 1 + 2 ( b 2 b 2 − 1 + 1 δ b 3 b 2 − 1 ); furthermore, we show again that this upper bound is tight. Last, for general k-bit hints, we show upper bounds for general k-bit hints, as well as lower bounds: specifically, we show that the consistency of any 9-robust strategy must be at least 5, and that the consistency of r-robust strategies is at least 1 + 2 b r / ( b r − 1 ), in the case of a natural class of asymptotic strategies.

IJCAI Conference 2022 Conference Paper

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 problem, in which a sequence of items of various sizes must be placed into a minimum number of bins of uniform capacity. The online algorithm is enhanced with a (potentially erroneous) prediction concerning the frequency of item sizes in the sequence. We design and analyze online algorithms with efficient tradeoffs between the consistency (i. e. , the competitive ratio assuming no prediction error) and the robustness (i. e. , the competitive ratio under adversarial error), and whose performance degrades near-optimally as a function of the prediction error. This is the first theoretical and experimental study of online bin packing in the realistic setting of learnable predictions. Previous work addressed only extreme cases with respect to the prediction error, and relied on overly powerful and error-free oracles.

AAAI Conference 2022 Conference Paper

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 each revealed price, the player must decide irrevocably whether to accept or reject it, without knowledge of future prices (other than an upper and a lower bound on their extreme values), and the objective is to minimize the competitive ratio, namely the worst case ratio between the maximum price in the sequence and the one selected by the player. The problem formulates several applications of decision-making in the face of uncertainty on the revealed samples. Previous work on this problem has largely assumed extreme scenarios in which either the player has almost no information about the input, or the player is provided with some powerful, and error-free advice. In this work, we study learningaugmented algorithms, in which there is a potentially erroneous prediction concerning the input. Specifically, we consider two different settings: the setting in which the prediction is related to the maximum price in the sequence, as well as well as the setting in which the prediction is obtained as a response to a number of binary queries. For both settings, we provide tight, or near-tight upper and lower bounds on the worst-case performance of search algorithms as a function of the prediction error. We also provide experimental results on data obtained from stock exchange markets that confirm the theoretical analysis, and explain how our techniques can be applicable to other learning-augmented applications.

AAAI Conference 2021 Conference Paper

Contract Scheduling With Predictions

• Spyros Angelopoulos
• Shahin Kamali

Contract scheduling is a general technique that allows to design a system with interruptible capabilities, given an algorithm that is not necessarily interruptible. Previous work on this topic has largely assumed that the interruption is a worstcase deadline that is unknown to the scheduler. In this work, we study the setting in which there is a potentially erroneous prediction concerning the interruption. Specifically, we consider the setting in which the prediction describes the time that the interruption occurs, as well as the setting in which the prediction is obtained as a response to a single or multiple binary queries. For both settings, we investigate tradeoffs between the robustness (i. e. , the worst-case performance assuming adversarial prediction) and the consistency (i. e, the performance assuming that the prediction is error-free), both from the side of positive and negative results.

AAAI Conference 2021 Conference Paper

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 consider online search, in which the performance of the search strategy is evaluated by its worst case competitive ratio. We introduce a multi-criteria search problem in which the searcher has a budget on its allotted search time, and the objective is to design strategies that are competitively efficient, respect the budget, and maximize the total searched ground. We give analytically optimal strategies for the line and the star environments, and efficient heuristics for general networks.

TCS Journal 2021 Journal Article

Preface to the special issue on Graph Searching: Theory and Applications

• Spyros Angelopoulos
• Nancy E. Clarke
• Fedor V. Fomin
• Archontia C. Giannopoulou
• Roman Rabinovich

IJCAI Conference 2019 Conference Paper

Earliest-Completion Scheduling of Contract Algorithms with End Guarantees

• Spyros Angelopoulos
• Shendan Jin

We consider the setting in which executions of contract algorithms are scheduled in a processor so as to produce an interruptible system. Such algorithms offer a trade off between the quality of output and the available computation time, provided that the latter is known in advance. Previous work on this setting has provided strict performance guarantees for several variants of this setting, assuming that an interruption can occur arbitrarily ahead in the future. In practice, however, one expects that the schedule will reach a point beyond which further progress will only be marginal, hence it can be deemed complete. In this work we show how to optimize the time at which the system reaches a desired performance objective, while maintaining interruptible guarantees throughout the entire execution. The resulting schedule is provably optimal, and it guarantees that upon completion each individual contract algorithm has attained a predefined end guarantee.

TCS Journal 2019 Journal Article

Preface to special issue on Theory and Applications of Graph Searching

• Spyros Angelopoulos
• Nicolas Nisse
• Dimitrios M. Thilikos

TCS Journal 2017 Journal Article

Infinite linear programming and online searching with turn cost

• Spyros Angelopoulos
• Diogo Arsénio
• Christoph Dürr

We consider the problem of searching for a hidden target in an environment that consists of a set of concurrent rays. Every time the searcher turns direction, it incurs a fixed cost. The objective is to derive a search strategy for locating the target as efficiently as possible, and the performance of the strategy is evaluated by means of the well-established competitive ratio. In this paper we revisit an approach due to Demaine et al. [8] based on infinite linear-programming formulations of this problem. We first demonstrate that their definition of duality in infinite LPs can lead to erroneous results. We then provide a non-trivial correction which establishes the optimality of a certain round-robin search strategy.

IJCAI Conference 2015 Conference Paper

Further Connections Between Contract-Scheduling and Ray-Searching Problems

• Spyros Angelopoulos

This paper addresses two classes of different, yet interrelated optimization problems. The first class of problems involves a robot that must locate a hidden target in an environment that consists of a set of concurrent rays. The second class pertains to the design of interruptible algorithms by means of a schedule of contract algorithms. We study several variants of these families of problems, such as searching and scheduling with probabilistic considerations, redundancy and fault-tolerance issues, randomized strategies, and trade-offs between performance and preemptions. For many of these problems we present the first known results that apply to multi-ray and multi-problem domains. Our objective is to demonstrate that several wellmotivated settings can be addressed using a common approach.

TCS Journal 2014 Journal Article

Multi-target ray searching problems

• Spyros Angelopoulos
• Alejandro López-Ortiz
• Konstantinos Panagiotou

We consider the problem of exploring m concurrent rays using a searcher. The rays are disjoint with the exception of a single common point, and in each ray at most one potential target may be located. The objective is to design search strategies for locating t targets (with t ⩽ m ) while minimizing the search distance traversed. This setting generalizes the extensively studied ray search (or star search) problem, in which the searcher seeks a single target. We apply two different measures for evaluating the efficiency of the search strategy. The first measure is the standard metric in the context of ray-search problems, and compares the total search cost to the cost of an optimal algorithm that has full information on the targets. We present a simple strategy that achieves optimal competitive ratio under this metric. Our main result pertains to the second measure, which is based on a weakening of the optimal cost as proposed by Kirkpatrick [ESA 2009] and McGregor et al. [ESA 2009]. For this model, we present an asymptotically optimal strategy that is within a multiplicative factor of Θ ( log ( m − t ) ) from the optimal search cost. Our results demonstrate that, for both problems, the problem of locating t targets in m rays is essentially as difficult as the problem of locating a single target in m − ( t − 1 ) rays.

TCS Journal 2010 Journal Article

Randomized priority algorithms

• Spyros Angelopoulos
• Allan Borodin

Borodin, Nielsen and Rackoff [13] introduced the class of priority algorithms as a framework for modeling deterministic greedy-like algorithms. In this paper we address the effect of randomization in greedy-like algorithms. More specifically, we consider approximation ratios within the context of randomized priority algorithms. As case studies, we prove inapproximation results for two well-studied optimization problems, namely facility location and makespan scheduling.

IJCAI Conference 2009 Conference Paper

• Spyros Angelopoulos
• Alejandro López-Ortiz

In this paper we address the problem of designing an interruptible system in a setting in which n problem instances, all equally important, must be solved. The system involves scheduling executions of contract algorithms (which offer a tradeoff between allowable computation time and quality of the solution) in m identical parallel processors. When an interruption occurs, the system must report a solution to each of the n problem instances. The quality of this output is then compared to the best-possible algorithm that has foreknowledge of the interruption time and must, likewise, produce solutions to all n problem instances. This extends the well-studied setting in which only one problem instance is queried at interruption time. We propose a schedule which we prove is optimal for the case of a single processor. For multiple processors, we show that the quality of the schedule is within a small factor from optimal.

AAAI Conference 2008 Conference Paper

Optimal Scheduling of Contract Algorithms with Soft Deadlines

• Spyros Angelopoulos

A contract algorithm is an algorithm which is given, as part of its input, a specified amount of allowable computation time. In contrast, interruptible algorithms may be interrupted throughout their execution, at which point they must report their current solution. Simulating interruptible algorithms by means of schedules of executions of contract algorithms in parallel processors is a well-studied problem with significant applications in AI. In the classical case, the interruptions are hard deadlines in which a solution must be reported immediately at the time the interruption occurs. In this paper we study the more general setting of scheduling contract algorithms at the presence of soft deadlines. This is motivated by the observation of practitioners that soft deadlines are as common an occurrence as hard deadlines, if not more common. In our setting, at the time t of interruption the algorithm is given an additional window of time w(t) ≤ c · t to continue the contract or, indeed, start a new contract (for some fixed constant c). We explore this variation using the acceleration ratio, which is the canonical measure of performance for these schedules, and derive schedules of optimal acceleration ratio for all functions w.