### Wednesday, July 15

## MS18

Approximation Algorithms(Part I of II)

10:30 AM-12:30 PM

*Room: Sidney Smith 2110*

Approximation algorithms have emerged as a major tool for coping with intractability of problems. The approximation algorithms approach is particularly suitable for use in the context of integer programming algorithms because the analysis provides a feasible approximate solution as well as a "bound" that leads to an estimate on the gap between the optimal and the feasible solutions. The field has pioneered the use of linear programming and semidefinite programming in worst case error analysis. Also, results of a negative nature establish that much of the recent work is the best possible under complexity limitations. There are current efforts to unify the ad hoc techniques that have been used for approximation algorithms. The presentations in this symposium reflect some of this latest emphasis on general purpose approaches and their applicability.

For Part II, see MS21.

**Organizer: Dorit S. Hochbaum**

*University of California, Berkeley*
**10:30 Gadgets, Approximation, and Linear Programming**
- David P. Williamson, IBM T. J. Watson Research Center
**11:00 Approximation Algorithms for Facility Location Problems**
*David B. Shmoys* and Fabián A. Chudak, Cornell University
**11:30 A Primal-Dual Interpretation of 2-Approximation Algorithms for the Feedback Vertex Set Problem in Undirected Graphs**
- Fabián A. Chudak, Cornell University

*MMD, 5/29/98*