Section outline

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

    • Weighted Set Cover: απόδειξη του λόγου Hn του άπληστου αλγόριθμου. Το πρόβλημα Maximum Coverage. Το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem), μη-προσεγγισιμότητα του γενικού προβλήματος. 2-προσεγγιστικός αλγόριθμος για το Metric TSP.

    Διαφάνειες: 31-45.

    Προτεινόμενη μελέτη: Vazirani άσκηση 2.15 (δείτε επίσης την ενότητα 2.3 για μια ενδιαφέρουσα εφαρμογή) και 3.2, και DPV 5.4, 9.2.3

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

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