You are here
28.11.2013: Min-Sum 2-Paths Problems
Submitted by admin on 05.04.24
28.11.2013 13:15–14:00
HIIT seminar
Exactum, CK111
Title
Min-Sum 2-Paths Problems
Abstract
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
