Section outline

    • Διάλεξη 18/2/2026. Εισαγωγή - Διαδικαστικά. Online learning, learning from experts advice: αλγόριθμοι weighted majority και randomized weighted majority.
    • Διάλεξη 24/2/2026. PAC Learning: μοντέλο, ορισμός, δειγματική πολυπλοκότητα, Empirical Risk Minimization (ERM), VC-dimension και θεμελιώδες θεώρημα στατιστικής μάθησης, ομοιόμορφη και ανομοιόμορφη σύγκλιση, surrogate loss functions, υπολογιστικά προβλήματα που προκύπτουν στην μηχανική μάθηση. Προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, 2-προσέγγιση του Vertex Cover, 2 και 1.5 προσεγγίσεις του metric TSP.
    • Διάλεξη 3/3/2026. Προσεγγιστικοί αλγόριθμοι: το πρόβλημα (Weighted) Set Cover. Ανάλυση λόγου προσέγγισης του άπληστου αλγόριθμου. Tight examples. Το πρόβλημα Maximum Coverage: (1-1/e)-προσεγγιστικός αλγόριθμος. Ψευδοπολυωνυμικοί αλγόριθμοι και προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS).FPTAS για το πρόβλημα Knapsack.
    • Διάλεξη 10/3/2026. Προσεγγιστικοί αλγόριθμοι: άπληστος αλγόριθμος για το πρόβλημα Set Cover και το πρόβλημα Maximum Coverage. FPTAS για το πρόβλημα Knapsack. Αναγωγές που στοχεύουν σε σημαντική διαφορά (gap) στην αντικειμενική τιμή της ενδεδειγμένης λύσης και μη προσεγγισιμότητα. Μη προσεγγισιμότητα του Travelling Salesman Problem. Εισαγωγή στον γραμμικό προγραμματισμό: βασικές έννοιες, μοντελοποίηση προβλημάτων συνδυαστικής βελτιστοποίησης με (ακέραιο) γραμμικό προγραμματισμό, γεωμετρία, κορυφές, βασικό θεώρημα γραμμικού προγραμματισμού.
    • Διάλεξη 24/3/2026. Γραμμικός προγραμματισμός: μοντελοποίηση συνδυαστικών προβλημάτων ως ακέραια γραμμικά προγράμματα (π.χ., vertex cover, set cover, maximum matching, TSP). Κορυφές πολυτόπου, βασικό θεώρημα γραμμικού προγραμματισμού (διαίσθηση και απόδειξη), βασικές εφικτές λύσεις, σχέση κορυφών πολυτόπου και βασικών εφικτών λύσεων. Η μέθοδος simplex.
    • Διάλεξη 31/3/2026. Η μέθοδος simplex. (Απλή) αναφορά σε άλλες αλγοριθμικές προσεγγίσεις για την επίλυση γραμμικών προγραμμάτων (αλγόριθμος ελλειψοειδούς, μέθοδοι εσωτερικού σημείου). Δυϊκότητα στο γραμμικό προγραμματισμό: πρωτεύων και δυϊκό, ασθενής δυϊκότητα, ισχυρή δυϊκότητα στον γραμμικό προγραμματισμό.
    • Διάλεξη 21/4/2026. Δυϊκότητα στον γραμμικό προγραμματισμό: complementary slackness conditions. (Απλή) αναφορά στη μέθοδο primal-dual. Προσεγγιστικοί αλγόριθμοι βασισμένοι στον γραμμικό προγραμματισμό, η βασική ιδέα / προσέγγιση του να χρησιμοποιήσουμε γραμμικό προγραμματισμό για να σχεδιάσουμε και να αναλύσουμε προσεγγιστικούς αλγόριθμους, ντετερμινιστική και τυχαία στρογγυλοποίηση (deterministic and randomized rounding) για το πρόβλημα Set Cover.
    • Διάλεξη 28/4/2026. Προσεγγιστικοί αλγόριθμοι βασισμένοι στον γραμμικό προγραμματισμό: βασική ιδέα, ILP formulations και LP relaxations, integrality gap, το (απλό αλλά κατατοπιστικό) παράδειγμα του knapsack (ILP formulation, LP relaxation, integrality gap με αντικείμενα μεγαλύτερα από το σακίδιο και χωρίς αυτά, αλγόριθμος με λόγο προσέγγισης 2 βασισμένος σε στρογγυλοποίηση), τυχαία στρογγυλοποίηση (randomized rounding) για το πρόβλημα Set Cover, deterministic rounding για το πρόβλημα VLSI routing, ο λόγος προσέγγισης της τυχαίας ανάθεσης για το πρόβλημα MAX-k-SAT, αλγόριθμος προσέγγισης για το πρόβλημα MAX-SAT βασισμένος σε τυχαία στρογγυλοποίηση.
    • Διάλεξη 5/5/2026. Προσεγγιστικοί αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό: χρήση τυχαιότητας για τα προβλήματα Max-Cut και Max-k-Cut, Semidefinite Programming και o αλγόριθμος Goemans-Williamson για το πρόβλημα Max-Cut (δείτε και lecture notes). H πιθανοτική μέθοδος:  Lovasz Local Lemma (δείτε lecture notes για το LLL και εφαρμογές του), αλγοριθμική εκδοχή LLL - η μέθοδος της εντροπίας (δείτε lecture notes και lecture notes).
    • Διάλεξη 12/5/2026. Συγκέντρωση γύρω από τη μέση τιμή, Chernoff-Hoeffding bounds (δείτε τα παρακάτω lecture notes: Goemans-MIT, Tulsiani-TTIC, Rinaldo-CMU-set1 και Rinaldo-CMU-set2), εφαρμογές, τυχαία στρογγυλοποίηση για το πρόβλημα VLSI routing, τυχαία δειγματοληψία. Secretary problems (δείτε ακόμη εδώ για secretary problems). Prophet inequalities (δείτε και αυτές τις διαφάνειες για εφαρμογές της ανισότητας του προφήτη και ανάλυση του λόγου προσέγγισης).
    • Διάλεξη 19/5/2026. Κυρτότητα και τοπική αναζήτηση, τοπικά και ολικά μέγιστα. Βασική ανάλυση της Gradient Descent για convex και strongly convex συναρτήσεις. Online learning, regret, no-regret αλγόριθμοι, Follow the Leader (FTL) (ορισμός και ανάλυση του regret, αιτία για τη γραμμικότητα του regret). Ο ρόλος της ισχυρής κυρτότητας στην ευστάθεια αλγορίθμων της μορφής Follow the Leader, regularization, Follow the Regularized Leader (FTRL, ορισμός, παραμετροποίηση με βάση τον regularizer, ανάλυση του regret). FTRL με χρήση του τετραγώνου της L2 norm ως regularizer και Online Gradient Descent (OGD).
    • Διάλεξη 27/5/2026. Follow the Regularized Leader (FTRL - επανάληψη, ανάλυση του regret). FTRL με χρήση του negative entropy ως regularizer και Multiplicative Weight Updates (MWU) και Hedge. Bregman divergence και Mirror Descent. Σύντομη εισαγωγή στους βασικούς αλγόριθμους για stochastic και adversarial multi-armed bandits: Explore-Then-Commit, Successive Elimination, UCB, EXP3.