Section outline

  • 9/3
    • Προσεγγιστικοί αλγόριθμοι (slides 27-41): το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem), μη-προσεγγισιμότητα του γενικού προβλήματος και προσεγγισιμότητα του Metric TSP. Αλγόριθμος Χριστοφίδη. Το πρόβλημα Steiner Tree. Τα προβλήματα Mutiway Cut και Minimum k-Cut.
      Προτεινόμενη μελέτη      : Vazirani 3 και 4, και DPV 9.2.3.
      Προσοχή: οι διαφάνειες δεν είναι τελικές, θα ανέβει νεώτερη έκδοση σύντομα.