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.

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