Wednesday, July 15

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
Program Program Overview Program-at-a-Glance Program Updates Speaker Index Registration Hotel Transportation

MMD, 5/29/98