Algorithmic Techniques for Network Connectivity Problems
Dr. Adrian Vetta, MIT
Monday March 25th.
Abstract. The task of finding low-cost subgraphs of a prescribed connectivity is a fundamental problem in network optimisation. Within this broad framework there is much variation. The underlying graphs may be undirected or directed and induce diverse cost structures. The connectivity constraints may concern edge or vertex connectivity, and the prescribed connectivity requirements may be low or high. I will present some techniques that have proved useful, in a range of these problems, for designing efficient algorithms with good theoretical performance. These include: graph decomposition methods, techniques from matching theory, LP based connectivity augmentation methods, and the iterative rounding of LPs. This talk is based upon a collection of work, including work with Joseph Cheriyan and Santosh Vempala.