23 April - 29 April

25/4

• Γραμμικός προγραμματισμός για προσεγγιστικούς αλγορίθμους: μέθοδοι Rounding και Primal-Dual Schema (διαφ. 16-33). 
  Προτεινόμενη μελέτη: Vazirani κεφ. 14, 15.
• Μη προσεγγισιμότητα με χρήση PCP. Το πρόβλημα Max3Sat: δυσκολία προσέγγισης και προσεγγισιμότητα (derandomization με τη μέθοδο των conditional expectations). [Παρουσίαση: Β. Μαργώνης]