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