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. Προσεγγιστικοί αλγόριθμοι βασισμένοι στον γραμμικό προγραμματισμό, η βασική ιδέα / προσέγγιση του να χρησιμοποιήσουμε γραμμικό προγραμματισμό για να σχεδιάσουμε και να αναλύσουμε προσεγγιστικούς αλγόριθμους, ILP formulations και LP relaxations,τυχαία στρογγυλοποίηση (randomized rounding) για το πρόβλημα Set Cover, randomized (και deterministic) rounding για το πρόβλημα VLSI routing.