Section outline

  • 27/2
    • Προσεγγιστικοί αλγόριθμοι: το πρόβλημα Set Cover με βάρη, H_n-προσεγγιστικός αλγόριθμος. Το πρόβλημα Maximum Coverage. Το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem), μη-προσεγγισιμότητα του γενικού προβλήματος και προσεγγισιμότητα του Metric TSP. Αλγόριθμος Χριστοφίδη. Το πρόβλημα Steiner Tree. Αναγωγές διατήρησης προσέγγισης.
    • Slides: 18-41
      Προτεινόμενη μελέτη: Vazirani 2.1 (δείτε και άσκηση 2.15, επίσης την ενότητα 2.3 για μια ενδιαφέρουσα εφαρμογή) και 3, και DPV 5.4, 9.2.3