BARC Talk by Fabrizio Grandoni

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 the 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. 

SHORT BIO
Prof. Fabrizio Grandoni received a Ph.D. in Computer Science in 2004 from the University of Rome Tor Vergat. During his Ph.D., he visited MPII with a Marie-Curie fellowship. After postdoc positions at MPII, University of Rome Sapienza and TU Berlin, in 2007 he joined the University of Rome Tor Vergata as an Assistant Professor. In 2011 he moved to the Dalle Molle Institute for Artificial Intelligence of Lugano, Switzerland, first as a Research Professor and then (from 2019) as a Professor.

His research is focused on the design and (mostly theoretical) analysis of algorithms and data structures.  His main area of research is approximation algorithms, but he is also interested in efficient algorithms and data structures, dynamic algorithms, online algorithms, parameterized algorithms, and distributed algorithms. He currently has 126 publications (42 journals) with 111 coauthors. Among his 79 peer-reviewed conference papers, 32 are CORE A* and 37 are CORE A. According to Google Scholar his papers received over 4500 citations and his H-index is 38.

 He received (with his coauthors) the best STOC paper Award in 2010, and the Nerode Prize in 2017. He received funding (as PI) totalling about 4 million EUR, including an ERC Starting Grant in 2012. Since 2021 he is a member of the Swiss National Research Council, and a full member of the European Association for Theoretical Computer Science. 

Fabrizio Grandoni will be visiting BARC from Monday the 15th of May until Friday the 19th of May.