Section outline

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