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).