If you do not see this message displayed properly, please click here


The Faculty of Informatics is pleased to announce a seminar given by Bundit Laekhanukit



Designing Fault-Tolerant Networks via Rounding-by-Tree-Embedding
Speaker: Bundit Laekhanukit
The Weizmann Institute of Science, Israel
Date: Friday, March 17, 2017
Place: USI Lugano Campus, room SI-006, Informatics building (Via G. Buffi 13)
Time: 09:30



Designing a network in a cost-effective way is a major goal in network design, which has been an important subject in Combinatorial Optimization and Theoretical Computer Science. In this talk, we present algorithms that design cost-efficient asymmetric network that can function under failure conditions (link or node failures). Our algorithms use linear programming (LP) relaxations to suggest which links should be included in the network. The key feature of our linear programs is that they capture the work of brute-force (exponential-time) algorithms, which thus allows us to forcefully embed a feasible (fractional) LP solution into a tree. This aids our decision in designing a network. We apply our technique to network design problems: Group Steiner Tree, Fault-Tolerant Group Steiner Tree, Fault-Tolerant Directed Steiner Tree, thus giving progress for all the mentioned problems.

This talk is based on joint works with Parinya Chalermsook, Syamantak Das, Fabrizio Grandoni and Daniel Vaz.



Bundit Laekhanukit is a postdoctoral fellow at the Weizmann Institute of Science in Israel, where he is supervised by Prof. Uriel Feige and Prof. Robert Krauthgamer. He received his PhD in Computer Science from the McGill University in 2014 under the supervision of Prof. Adrian Vetta. After finishing his PhD, he was a research fellow at the Simons Institute for the Theory of Computing at UC Berkeley in Fall 2014. He then moved to the Swiss AI Lab IDSIA to work as a postdoctoral researcher. Since October 2015, he has joined the Weizmann Institute of Science as a postdoctoral fellow.

His research interest is algorithms and complexity with a focus on approximation algorithms and hardness of approximations.


Host: Prof. Kai Hormann


Faculty of Informatics

Faculty of Informatics
Università della Svizzera italiana
Via Giuseppe Buffi 13
CH-6904 Lugano
Tel.: +41 (0)58 666 46 90
Fax: +41 (0)58 666 45 36
Email: decanato.inf@usi.ch
Web: www.inf.usi.ch
Twitter: @USI_INF


Segui USI@EXPO2015 su Twitter Segui USI@EXPO2015 su Facebook Segui USI@EXPO2015 su Linkedin Segui USI@EXPO2015 su YouTube