Sunday, January 9

Session 3A

1:30 PM-3:35 PM
Room: Gold Rush A

1:30 Cooperative Facility Location Games

Michel X. Goemans, Massachusetts Institute of Technology; and Martin Skutella, Technische Universität Berlin, Germany

1:55 K-Medians, Facility Location, and the Chernoff-Wald Bound

Neal E. Young, Dartmouth College

2:20 Improved Approximation Algorithms for MAX SAT

Takao Asano, Chuo University, Japan; and David P. Williamson, IBM T. J. Watson Research Center

2:45 Strengthening Integrality Gaps for Capacitated Network Design and Covering Problems

Robert D. Carr, Sandia National Laboratories, Albuquerque; Lisa K. Fleischer, Columbia University; Vitus J. Leung, and Cynthia A. Phillips, Sandia National Laboratories, Albuquerque

3:10 Towards a 4/3 Approximation for the Asymmetric Traveling Salesman Problem

Robert D. Carr, Sandia National Laboratories, Albuquerque; and Santosh Vempala, Massachusetts Institute of Technology