6 Μαρτίου - 12 Μαρτίου

6/3

• Προσεγγιστικοί αλγόριθμοι (slides 42-44): Τα προβλήματα Mutiway Cut και Minimum k-Cut.
  Προτεινόμενη μελέτη: Vazirani κεφ. 4.
• Προσεγγιστικοί αλγόριθμοι (2η ενότητα, slides 25-34): ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα (Discrete) Knapsack.
  Προτεινόμενη μελέτη: Vazirani κεφ. 8.
  
• Προσεγγιστικοί αλγόριθμοι (3η ενότητα): το πρόβλημα Minimum Makespan Scheduling. Ισχυρή NP-πληρότητα (αναγωγή από 3-PARTITION) και προσεγγιστικοί αλγόριθμοι: 2-προσεγγιστικός, (4/3)-προσεγγιστικός, PTAS (απλή αναφορά).
  Προτεινόμενη μελέτη: Vazirani κεφ. 10.