On 12 March, Pedro Matias, PhD student in Theoretical Computer Science at University of California, Irvine, will give a talk entitled "How to Catch Marathon Cheaters: New Approximation Algorithms for Tracking Paths" in the following zoom link: http://bit.ly/ALGOtalksPedroMatias.
ALGO talks is a seminar series organized by the ALGorithms and Optimization Lab, Adaptive Computation Group, CISUC and University of Coimbra.
Given an undirected graph, G, and vertices, s and t in G, the tracking paths problem is that of finding the smallest subset of vertices in G whose intersection with any s-t path results in a unique sequence. This problem is known to be NP-complete and has applications to animal migration tracking and detecting marathon course-cutting, but its approximability is largely unknown. In this talk, we address this latter issue, giving novel algorithms having approximation ratios of (1+ε), O(lg OPT) and O(lg n), for H-minor-free, general, and weighted graphs, respectively. We also give a linear kernel for H-minor-free graphs.
Pedro is finishing his PhD in Theoretical Computer Science at Univ. California, Irvine and his thesis topic concerns the exact learning of sequences using adaptive and nonadaptive queries. Previously, he was at Chalmers Univ. of Technology, where he obtained his M.Sc. degree in Computer Science. Before that, he obtained his B.Sc. degree in Informatics Engineering from University of Coimbra, where he worked with Luís Paquete on Multiobjective Optimization.