Section outline

  • Διάλεξη 18/3: Προσεγγιστικοί αλγόριθμοι Ι

    • Εισαγωγή στους προσεγγιστικούς αλγορίθμους. Προβλήματα Vertex Cover και Set Cover με και χωρίς βάρη. Ο λόγος προσέγγισης του άπληστου αλγόριθμου (Greedy).

    Διαφάνειες (προσωρινή έκδοση): 1-32.

    Προτεινόμενη μελέτη: Vazirani κεφ. 1 (κυρίως 1.1), 2.1 και 2.2. Επίσης: DPV 9.2.1.

    Το μάθημα πραγματοποιήθηκε διαδικτυακά. Σύνδεσμοι για τα βίντεο της διάλεξης:

    (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).