Section outline

  • 17/4: Προσεγγιστικοί Αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό (συνέχεια),
    Εισαγωγή στην Αλγοριθμική Θεωρία Παιγνίων.
    • Primal-dual μέθοδος για το πρόβλημα set cover, αλγόριθμος Goemans-Williamson για το πρόβλημα MAX-CUT. 
      Προτεινόμενη μελέτη: D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Ενότητες: 7.1 - 7.6 (μέθοδος primal-dual για αλγόριθμους προσέγγισης), 6.1 - 6.3 (προσεγγιστικοί αλγόριθμοι βασισμένοι σε semidefinite programming relaxations), σημειώσεις για τον αλγόριθμο Goemans-Williamson, 1.6 (η μέθοδος dual fitting για set cover). 
    • Σύντομη εισαγωγή στην Αλγοριθμική Θεωρία Παιγνίων (διαφάνειες), παίγνια μηδενικού αθροίσματος, το θεώρημα Μinimax του von Neumann (διαφάνειες και διαφάνειες).
      Προτεινόμενη μελέτη: σημειώσεις για παίγνια μηδενικού αθροίσματος και το θεώρημα του Nash. 
      Anna R. Karlin and Yuval Peres. Game Theory, Alive. American Mathematical Society, 2016. Κεφάλαια: 2, 4 και 5.