Section outline

    • Διάλεξη 12/2/2025. Εισαγωγή - Διαδικαστικά. Εισαγωγή στους πιθανοτικούς αλγόριθμους, πιθανοτικός αλγόριθμος για το πρόβλημα Ελάχιστης Τομής (δείτε ακόμη wikipedia και σημειώσεις για τον αλγόριθμο Karger), πιθανοτικός αλγόριθμος για το πρόβλημα 2-SAT (δείτε και αυτές τις διαφάνειες για το 2-SAT).
    • Διάλεξη 19/2/2025. Πιθανοτικός αλγόριθμος για το πρόβλημα 3-SAT (δείτε και αυτές τις διαφάνειες για το 3-SAT), secretary problems (δείτε ακόμη εδώ για secretary problems). Prophet inequalities. Συγκέντρωση γύρω από τη μέση τιμή, Chernoff-Hoeffding bounds (δείτε lecture notes), εφαρμογές, τυχαία δειγματοληψία.
    • Διάλεξη 5/3/2025. Προσεγγιστικοί αλγόριθμοι. Βασικές Έννοιες. Ιεραρχία κλάσεων προσεγγισιμότητας. Το πρόβλημα Vertex Cover με και χωρίς βάρη, 2-προσεγγιστικοί αλγόριθμοι. 
    • Διάλεξη 12/3/2025. Προσεγγιστικοί αλγόριθμοι: το πρόβλημα (Weighted) Set Cover. Ανάλυση λόγου προσέγγισης του άπληστου αλγόριθμου (Greedy). Tight examples. Το πρόβλημα Maximum Coverage: (1-1/e)-προσεγγιστικός αλγόριθμος.
    • Διάλεξη 19/3/2025. Προσεγγιστικοί αλγόριθμοι: το πρόβλημα TSP, μη προσεγγισιμότητα. Προσεγγιστικοί αλγόριθμοι για το Metric TSP. Το πρόβλημα Steiner Tree. Αναγωγές διατήρησης προσεγγισιμότητας. 2-προσεγγιστικός αλγόριθμος για Steiner Tree.
    • Διάλεξη 26/3/2025. Προσεγγιστικοί αλγόριθμοι: προβλήματα τομών, Multiway Cut, Minimum k-Cut. Δένδρα Gomory-Hu. Ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα (Discrete) Knapsack. Διαφάνειες (25-34). 
    • Διάλεξη 2/4/2025. Ανισότητα προφήτη (επανάληψη και απόδειξη λόγου προσέγγισης). Online learning, learning from experts advice: αλγόριθμοι weighted majority και randomized weighted majority. 
    • Διάλεξη 11/4/2025. PAC learning, ERM, μάθηση με ομοιόμορφη και ανομοιόμορφη σύγκλιση, VC dimension, θεμελιώδες θεώρημα μηχανικής μάθησης.  Κυρτά σύνολα και κυρτή βελτιστοποίηση, η μέθοδος gradient descent. Εισαγωγή στο γραμμικό προγραμματισμό: γεωμετρία, κορυφές και βασικές εφικτές λύσεις.
    • Διάλεξη 30/4/2025. Εισαγωγή στον γραμμικό προγραμματισμό: γεωμετρία, κορυφές, βασικό θεώρημα γραμμικού προγραμματισμού, βασικές εφικτές λύσεις. Η μέθοδος simplex. Δυϊκότητα στο γραμμικό προγραμματισμό. 
    • Διάλεξη 5/5/2025. Δυϊκότητα στο γραμμικό προγραμματισμό. Προσεγγιστικοί αλγόριθμοι βασισμένοι στον γραμμικό προγραμματισμό, η βασική ιδέα / προσέγγιση του να χρησιμοποιήσουμε γραμμικό προγραμματισμό για να σχεδιάσουμε και να αναλύσουμε προσεγγιστικούς αλγόριθμους, ILP formulations και LP relaxations,τυχαία στρογγυλοποίηση (randomized rounding) για το πρόβλημα Set Cover, randomized (και deterministic) rounding για το πρόβλημα VLSI routing. Δείτε ακόμη την αντίστοιχη βιντεοσκοπημένη διάλεξη (από το 38ο λεπτό περίπου μέχρι το τέλος, κωδικός: Adv-Algo!2021+ ) για προσεγγιστικούς αλγόριθμους βασισμένους σε γραμμικό προγραμματισμό.
    • Διάλεξη 7/5/2025. Εισαγωγή σε παραμετρικούς αλγορίθμους και παραμετρική πολυπλοκότητα: 
    • Διάλεξη 12/5/2025. Προσεγγιστικοί αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό: χρήση τυχαιότητας για τα προβλήματα Max-Cut, Max-k-Cut, Max-k-SAT, Semidefinite Programming και o αλγόριθμος Goemans-Williamson για το πρόβλημα Max-Cut (δείτε και lecture notes). Εισαγωγή στον σχεδιασμό μηχανισμών. Δημοπρασίες για ένα αντικείμενο. Η δημοπρασία 2ης τιμής. Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson. (σημειώσεις το μάθημα του Tim Roughgarden: σχεδιασμός μηχανισμών και Myerson's Lemma).
    • Διάλεξη 21/5/2025. Παραμετρική πολυπλοκότητα. Παραμετρικές αναγωγές. W[1]-hardness των  (Multicolored) Independent Set, Dominating set, Set Cover. W-hierarchy, weft. Διαφάνειες (1-20).