### 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

*Created 11/7/99; Last Updated 11/7/99 *