Speaker:
Time:
Venue:
- A-212 (STCS Seminar Room)
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).