mwang (02/15/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
_T_H_E_O_R_Y _S_E_M_I_N_A_R - Thursday, February 24, 1983.
Mr. Joseph Peters of the University of Toronto will speak on
``_T_i_m_e-_A_c_c_u_r_a_c_y _T_r_a_d_e-_O_f_f_s _f_o_r _N_P-_h_a_r_d _P_r_o_b_l_e_m_s''.
_T_I_M_E: 3.30PM
_R_o_o_m: MC 5158
ABSTRACT
An oracle model of computation for proving lower bounds on
the time to find approximate solutions of guaranteed accura-
cy for NP-hard optimization problems will be discussed. Two
lower bounds are then derived. For the 0-1 Knapsack prob-
lem, a lower bound polynomial in both the size of the in-
stance and the inverse of the accuracy requirement is shown.
For the Max Clique problem an exponential lower bound is
proved. Both bounds have the same form as the best known
upper bounds. The oracles correspond to matroid axioms and
are from the class P.
February 15, 1983