Min-Sum 2-Paths Problems

Lecturer : 
Alex Popa
Event type: 
HIIT seminar
Event time: 
2013-11-28 13:15 to 14:00
Exactum, CK111
Min-Sum 2-Paths Problems
An orientation of an undirected graph $G$ is a directed graph obtained by replacing each edge $\{u,v\}$ of $G$ by exactly one of the arcs $(u,v)$ or $(v,u)$.
In the min-sum $2$-paths orientation problem, the input is an undirected graph $G$ and two ordered pairs $(s_1,t_1)$, $(s_2,t_2)$. The goal is to find an orientation of $G$ that minimizes the sum of the distances from $s_1$ to $t_1$ and $s_2$ to $t_2$.
In this talk we present a PTAS for this problem and show a connection with the more famous min-sum $2$ edge disjoint paths problem, where we are searching for two edge disjoint paths of minimum total length.
About the presenter
Alex Popa completed his PhD at the University of Bristol in 2011. Then, he was a post-doc at Aalto University for two years and currently he is an Assistant Professor at Masaryk University in Brno, Czech Republic. His research interests are: algorithms for NP-hard problems, string algorithms and bioinformatics.
You can find more information on his web-page: http://fi.muni.cz/~popa.

Last updated on 20 Nov 2013 by Brandon Malone - Page created on 20 Nov 2013 by Brandon Malone