Section outline

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

    • Προσεγγιστικοί αλγόριθμοι (slides 47-56): Το πρόβλημα Steiner Tree και Metric Steiner Tree. Αναγωγές διατήρησης προσέγγισης. Τα προβλήματα Mutiway Cut και Minimum k-Cut.
      Προτεινόμενη μελέτη      : Vazirani κεφ. 3.1 και 4.
    • Προσεγγιστικοί αλγόριθμοι (2η ενότητα, slides 25-34): ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα (Discrete) Knapsack.
      Προτεινόμενη μελέτη: Vazirani κεφ. 8.
    • Προσεγγιστικοί αλγόριθμοι (3η ενότητα): το πρόβλημα Minimum Makespan Scheduling. Ισχυρή NP-πληρότητα (αναγωγή από 3-PARTITION) και προσεγγιστικοί αλγόριθμοι: 2-προσεγγιστικός, (4/3)-προσεγγιστικός, PTAS (σύντομη αναφορά).
      Προτεινόμενη μελέτη: Vazirani κεφ. 10.

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

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