Section outline

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

    • Αλγόριθμος Χριστοφίδη για το Metric TSP. Αλγόριθμος Hoogeveen για το πρόβλημα TSP(s-t path).
    • Το πρόβλημα Steiner Tree και Metric Steiner Tree. Αναγωγές διατήρησης προσέγγισης.
    • Τα προβλήματα Mutiway Cut και Minimum k-Cut.

      Διαφάνειες      : 46-58.

      Προτεινόμενη μελέτη: Vazirani κεφ. 3.1 και 4.

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

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