16 April - 22 April

18/4

• Εισαγωγή στην δυϊκότητα. Πρωτεύον και δυϊκό πρόγραμμα. Ασθενής και ισχυρή δυϊκότητα. Complementary slackness conditions.
  Προτεινόμενη μελέτη: Vazirani κεφ. 12.
• Γραμμικός προγραμματισμός για προσεγγιστικούς αλγορίθμους: η μέθοδος Dual Fitting για το πρόβλημα Set Cover (διαφ. 1-9). 
  Προτεινόμενη μελέτη: Vazirani κεφ. 13.1.