Designing Fault-Tolerant Networks via Rounding-by-Tree-Embedding

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.