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. Εισαγωγή στον γραμμικό προγραμματισμό: βασικές έννοιες, μοντελοποίηση προβλημάτων συνδυαστικής βελτιστοποίησης με (ακέραιο) γραμμικό προγραμματισμό, γεωμετρία, κορυφές, βασικό θεώρημα γραμμικού προγραμματισμού.