Section outline

  • 23/3
    • Προσεγγιστικοί αλγόριθμοι (3η ενότητα): προσεγγιστικό σχήμα (PTAS) για το πρόβλημα Minimum Makespan Scheduling με αναγωγή στο Restricted Bin Packing. Ακριβής αλγόριθμος δυναμικού προγραμματισμού για το Restricted Bin Packing.
      Προτεινόμενη μελέτη: Vazirani κεφ. 10.
    • Γραμμικός προγραμματισμός: εισαγωγή, τυπική και κανονική μορφή, πολύεδρο εφικτών λύσεων, βασικές εφικτές λύσεις (διαφ. 1-12).
      (ανέβηκε νέα έκδοση).
      Προτεινόμενη μελέτη: DPV 7.1 (δείτε και Karloff κεφ. 1 για μια πιο αναλυτική παρουσίαση, καθώς και τις πολύ καλές διαφάνειες/σημειώσεις του μαθήματος LP του Henry Wolkowicz, U Waterloo, ενότητες 1-4 και 11-13).