Skip to content
Loading Events

« All Events

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.

Details

Date:
November 20
Time:
12:00 pm - 1:00 pm
Event Category:

Venue

Bharti 501
IIT Campus, Hauz Khas
New Delhi,
+ Google Map