Tuesday, January 7
10:25 AM-12:25 PM
Ile de France 2&3
Chair: David P. Williamson, IBM T. J. Watson Research Center

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

MMD, 10/22/96