Tata Institute of Fundamental Research
Network Design with Metric Costs
Colloquium
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).
| 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).