Section outline

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

    • Εισαγωγή στους προσεγγιστικούς αλγορίθμους. Το πρόβλημα Vertex Cover με και χωρίς βάρη, 2-προσεγγιστικοί αλγόριθμοι. Ανελαστικά φράγματα (tight bounds). Το πρόβλημα Set Cover: λόγος προσέγγισης του άπληστου αλγόριθμου (Greedy).

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

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

    Bίντεο της διάλεξης

    (ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό και ισχύουν περιορισμοί χρήσης, δείτε παραπάνω)