12 March - 18 March

14/3

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