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.
- S. Angelopoulos, A. López-Ortiz and R. Dorrigiv: On the separation and equivalence of paging strategies and other online algorithms (Algorithmica 2018).
- S. Angelopoulos and P. Schweitzer: Paging and list update under bijective analysis (Journal of the ACM 2013).
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.
S. Angelopoulos, D. Arsénio, C. Dürr and A. López-Ortiz: Multiprocessor search and scheduling problems with setup cost (Theory of Computing Systems, 2017).
S. Angelopoulos, Gioegio Lucareli, and KT Nguyen: Primal-Dual and Dual-Fitting Analysis of Online Scheduling Algorithms for Generalized Flow Time Problems (ESA 2015).
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.
S. Angelopoulos, C. Dürr and T. Lidbetter: The expanding search ratio of a graph (STACS 2016).
S. Angelopoulos: Further connections between contract-scheduling and ray-searching problems (IJCAI 2015).
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.
A. López-Ortiz, S. Angelopoulos and A. Hamel: Optimal scheduling of contract algorithms for anytime problems (Journal of AI Research 2014).
S. Angelopoulos and A. López-Ortiz: Optimal scheduling of contract algorithms with soft deadlines (Journal of Scheduling, 2017).