Keynote Speakers
Fabrizio Grandoni
IDSIA, USI-SUPSI
Title: Unsplittable Flow on a Path and Related Problems
Abstract: In the unsplittable flow on a path problem (UFP) we are given a path graph with edge capacities. Furthermore we are given a collection of n tasks, where each task is characterized by a subpath, a demand, and a profit. Our goal is to select a maximum profit subset of tasks such that the total demand of selected tasks using each edge e does not exceed the capacity of e. We might interpret the path as a time horizon subdivided into time slots (the edges). In this scenario, each task has to be executed in a specific time interval or not at all, and, if executed, it demands for a given amount of a time-varying resource (e.g., energy) and it provides a given revenue.
I will overview the main results on the approximability of this NP-hard problem, culminating with a recent PTAS. I will also mention some related problems and open questions.
Luca Aceto
Reykjavik University and Gran Sasso Science Institute
Title: A journey through the spectrum of monitorability
Abstract: Runtime verification is a dynamic and lightweight approach to the verification of computing systems. It is based on the analysis of the events systems perform as they execute and uses the result of that analysis to find bugs. In light of its flexibility and wide range of applicability, this technique has become increasingly popular in many areas of computer science, and has the been the subject of extensive research both within the “Track A” and “Track B” communities.
Monitorability provides the theoretical foundations for runtime verification because it delineates what properties can be verified at runtime and should inform the design of software tools that automate the runtime-verification process. But when is a system property monitorable? The literature presents a plethora of definitions of the notion of “monitorability”, few of which are given explicitly in terms of the operational guarantees provided by monitors, which are the computational entities carrying out the verification at runtime.
In this talk, I will argue that monitorability should be viewed as a spectrum, where the fewer guarantees that are required of monitors, the more properties become monitorable. I will present a monitorability hierarchy based on this trade-off, discuss variations on the resulting spectrum and argue for the importance of syntactic characterisations of the monitorable properties.
I will close the talk by highlighting avenues for future work that might be of interest to theoretical computer scientists, regardless of their “track allegiance”.
This presentation is based on joint work with several colleagues and students, including Antonis Achilleos (Reykjavik University), Elli Aastasiadi (Reykjavik University), Duncan Paul Attard (Reykjavik University and University of Malta), Ian Cassar (Reykjavik University and University of Malta), Adrian Francalanza (University of Malta), Anna Ingólfsdóttir (Reykjavik University) and Karoliina Lehtinen (CNRS, Aix-Marseille Université, LIS).