Approximation Algorithms for Capacitated Network Design by Prof. Joseph Cheriyan
November 20 @ 12:00 pm - 1:00 pm
Abstract:
This is a “non-specialist” talk on a couple of results from a 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 Ishan Bansal, Logan Grout, Sharat Ibrahimpur, Sanjeev Khanna, and Miles Simmons.
