Tuesday, January 11

Session 11A

1:45 PM-3:50 PM
Room: Gold Rush A

1:45 A 2 + e Approximation Algorithm for the k-MST Problem
Sanjeev Arora and George Karakostas, Princeton University
2:10 The Prize Collecting Steiner Tree Problem: Theory and Practice
David S. Johnson, AT&T Labs - Research; Maria Minkoff, Massachusetts Institute of Technology; and Steven Phillips, AT&T Labs - Research
2:35 Improved Steiner Tree Approximation in Graphs
Gabriel Robins, University of Virginia; and Alexander Zelikovsky, Georgia State University
3:00 The Rectilinear Steiner Arborescence Problem is NP-Complete
Weiping Shi and Chen Su, University of North Texas
3:25 Improved Bandwidth Approximation for Trees
Anupam Gupta, University of California, Berkeley

© 1999, Society for Industrial and Applied Mathematics
Designed by Donaghy's Web Consulting
Created 11/7/99; Last Updated 11/7/99