Sunday, January 17
Session 8
Network Design
1:30 PM-2:30 PM
Room: Liberty B
Chair: Joan Feigenbaum, AT&T Laboratories Research
- 1:30-1:47 A 1.598 Approximation Algorithm for the Steiner
Problem in Graphs
- Stefan Hougardy and Hans Jürgen Prömel,
Humboldt-Universität zu Berlin, Germany
- 1:50-2:07 On the Bidirected Cut Relaxation for the Metric
Steiner Tree Problem
- Sridhar Rajagopalan, IBM Almaden Research Center; and Vijay
Vazirani, Georgia Institute of Technology
- 2:10-2:27 A Primal-Dual Schema Based Approximation Algorithm
for the Element Connectivity Problem
- Kamal Jain, Ion Mandoiu and Vijay V. Vazirani, Georgia Institute
of Technology; and David P. Williamson, IBM T. J. Watson Research Center
tjf, 9/12/98, MMD, 11/2/98