mwang@watmath.UUCP (mwang) (09/20/83)
_D_E_P_A_R_T_M_E_N_T _O_F _C_O_M_P_U_T_E_R _S_C_I_E_N_C_E _U_N_I_V_E_R_S_I_T_Y _O_F _W_A_T_E_R_L_O_O _S_E_M_I_N_A_R _A_C_T_I_V_I_T_I_E_S _C_O_M_P_U_T_E_R _S_C_I_E_N_C_E _C_O_L_L_O_Q_U_I_U_M - Wednesday, September 28, 1983. Dr. J. Bentley of Bell Laboratories will speak on ``A Case Study in Applied Algorithm Design: The Traveling Salesman Problem.'' TIME: 3.30 PM ROOM: MC 5158 ABSTRACT This talk describes the selection of a traveling sales- man algorithm for scheduling a mechanical plotter in a geopolitical database system. Although the choice of algorithm is tuned to the particular system, we will generalize from this case a methodology of Applied Al- gorithm Design that is broadly applicable. While the talk covers many aspects of applied algorithms (from problem definition to algorithm design to program im- plementation), the majority of the discussion will center around the techniques used to evaluate approxi- mation algorithms (or heuristics). Coffee and refreshments will be served at 3:00 PM. September 20, 1983