The purpose of this talk is to give some idea of the recent progress in obtaining strong, and sometimes tight, inapproximability constants for NP-hard optmization problems. Tight results have been obtained for Max-Ek-Sat for k>=3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting.
展开▼
