Monday, January 10

Session 5A

9:00 AM-10:40 PM
Room: Gold Rush A

9:00 On Local Search and Placement of Meters in Networks

Samir Khuller, University of Maryland, College Park; Randeep Bhatia, Bell Laboratories; and Robert Pless, University of Maryland, College Park

9:25 Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs

Eran Halperin, Tel-Aviv University, Israel

9:50 An Approximation Algorithm for the Covering Steiner Problem

Goran Konjevod, Carnegie Mellon University and Los Alamos National Laboratory; and R. Ravi, Carnegie Mellon University

10:15 On the Red-Blue Set Cover Problem

Robert D. Carr, Sandia National Laboratories, Albuquerque; Srinivas Doddi, Los Alamos National Laboratory; Goran Konjevod, Carnegie Mellon University and Los Alamos National Laboratory; and Madhav Marathe, Los Alamos National Laboratory