Tutte Colloquium - Joseph Cheriyan

Title: Approximation Algorithms for Flexible Graph Connectivity

Abstract: This is a "non specialist" talk on a couple of results from a long-running project in the area of capacitated network design. The key problem here is to find a sub-graph of minimum cost that satisfies a (global) edge connectivity requirement, where the input is a graph G that has a capacity u(e) and a cost c(e) for each edge e in E(G). (Note: The minimum spanning tree problem is the special case where the connectivity requirement is one and  all edge-capacities are one.)

The results in the talk are from joint work with Bansal, Grout, Ibrahimpur, Khanna, and Simmons.