Steiner Tree Approximation Via Iterative Randomized Rounding

The Faculty of Informatics is pleased to announce a seminar given by Fabrizio Grandoni

DATE: Tuesday, June 4th 2013
PLACE: USI Lugano Campus, room SI-008, Informatics building (Via G. Buffi 13)
TIME: 09.30

ABSTRACT:
Steiner tree is one of the most fundamental NP-hard problems: given an undirected graph, with non-negative edge costs, and a subset of terminal nodes, the goal is to compute a minimum-cost tree which contains all the terminals (Steiner tree).
Since there cannot be an efficient (i.e. worst-case polynomial-time) algorithm to solve the problem unless P=NP, a lot of research was devoted  to the design of approximation algorithms. We remind that an approximation algorithm for the problem is a polynomial-time algorithm which outputs a Steiner tree of cost at most rho times the cost of the optimum, for some value rho>1 (the "approximation factor"). In this talk we present the current best approximation algorithm for the problem, with approximation factor ln(4)+eps<1.39.
Our result exploits a novel linear-programming-based technique, iterative randomized rounding, which might be of independent interest.
(Joint work with J. Byrka, T. Rothvoss, and L. Sanità)

BIO:
Fabrizio Grandoni received a Ph.D. in Computer Science in 2004. He had PostDoc positions at the MPII of Saarbrucken (2004), at the Sapienza University of Rome (2004-2007), and at the Technical University of Berlin (2007). He also visited the University of Bergen (2006) and EPFL (2008,2009). He was an Assistant Professor at the Tor Vergata University of Rome between 2007 and 2011. He is a Senior Researcher at IDSIA since December 2011.
The work of Fabrizio Grandoni is focused on the theory of algorithms, in particular on approximation and exact/parameterized algorithms. He published over 70 papers in some of the top conferences and journals in Theoretical Computer Science. His publications received over 1400 citations. He served as a PC member of some of the main conferences in his research area. His work on Steiner tree approximation received the 2010 Best Paper Award at the ACM Symposium on Theory of Computing. In 2011 he was awarded an ERC Starting Grant for his project "New Approaches to Network Design".

HOST: Prof. Mauro Pezzè