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