Seminars at the Faculty of Informatics

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

á

Abstract:

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.

á

Biography:

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