Spyros Angelopoulos

Spyros Angelopoulos

CNRS and ILLS

Research highlights

Learning-augmented online algorithms

This nascent, and fast-growing area studies the power and limitations of algorithms that are enhanced with some machine-learned information about the instance. The objective is to design and analyze systems that remain robust under adversarial predictions, but perform well if the prediction is relatively reliable. Of particular interest are: query-based algorithms, where the advice is in the form of unreliable binary queries, and algorithms with provably learnable advice.

Representative publications:


Bijective analysis of online algorithms

Traditionally, online algorithms are analyzed by means of competitive analysis. However, the competitive ratio is often very pessimistic and does not always reflect the relative performance of algorithms in realistic settings. Can we do better? One idea is to compare algorithms pairwise, by establishing a dominance relation between the sets of costs of the two algorithms, using a bijective mapping between the two sets. For several online problems, this type of comparison yields theoretical results that reflect the empirical ones.

Representative publications:


Algorithmic aspects of search theory

Searching for a target is a common task in everyday life, but also an important computation problem with numerous applications (from drilling for oil in multiple locations to planning and executing search-and-rescue operations). The problems I consider typically involve a searcher who must locate a hider in an environment that may be known or unknown. The objective is to design and analyze efficient strategies for locating the target. In this broad class of problems one can find many variants depending on the cost definition, the optimization objectives etc; I am interested in combining tools from algorithm design (e.g., competitive analysis) and game theory (equilibria of search games) so as to identify efficient search strategies in various settings.

Representative publications:


Interruptible algorithms for anytime computation

Can one design algorithms that return meaningful solutions even if interrupted during their execution? This is a central question in anytime computation, with several applications in the design of real-time systems. I am interested in black-box techniques for converting algorithms with stringent requirements on running time (known as contract algorithms) to algorithms with interruptible characteristics. This gives rise to several scheduling and sequencing problems in which the jobs correspond to executions of contract algorithms, and the optimization objective describes the efficiency of the resulting simulation. This class of problems has surprising connections to search algorithms as well as online problems.

Representative publications:


Linear programming in (online) search and scheduling problems

I am interested in problems in which linear programming (and more generally, techniques from mathematical programming) can be applied so as to guide the design and analysis of efficient algorithms. This includes methods such as primal-dual, dual fitting, and various types of relaxations. For searching in unbounded domains, in particular, the resulting formulations may very well be infinite.

Representative publications: