Tata Institute of Fundamental Research

Network Design with Metric Costs

Speaker: Joseph Cheriyan University of Waterloo Canada http://www.math.uwaterloo.ca/~jcheriya/
Date: Wednesday, 29 Jul 2009 (all day)
Venue: A-212 (STCS Seminar Room)

(Scan to add to calendar)
Abstract:  A typical problem in network design is to find a subgraph H of a given graph G such that H satisfies some connectivity requirements and has minimum cost. We give a constant-factor approximation algorithm for network design with node-connectivity requirements of zero or k, assuming that the edge costs satisfy the triangle inequalities (joint work with A.Vetta, McGill University).