Session 19

10:25-10:45 Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem

Fatma Sihil Salman, Carnegie Mellon University; Joseph Cheriyan, University of Waterloo, Canada; Ramamoorthi Ravi, Carnegie Mellon University; and Sairam Subramanian, Northern Telecom, Dallas

10:50-11:10 A Better Approximation Ratio for the k-Edge-Connected Spanning Subgraph Problem

Cristina G. Fernandes, Georgia Institute of Technology

11:15-11:35 Fast Spreading Metric Based Approximate Graph Partitioning Algorithms

Guy Even, Universität des Saarlandes, Germany; Joseph Naor, Technion-Israel Institute of Technology, Israel; Satish Rao, NEC Research Institute; and Baruch Schieber, IBM T. J. Watson Research Center

11:40-12:00 Computing Edge-Connectivity Augmentation Function in O(nm) Time

Hiroshi Nagamochi, Takashi Shiraki, and Toshihide Ibaraki, Kyoto University, Japan

12:05-12:25 Efficient Algorithms for Robustness in Matroid Optimization

Greg N. Frederickson and Roberto Solis-Oba, Purdue University, West Lafayette

Registration | Hotel Information | Transportation | Program-at-a-Glance | Author Index