Section outline

  • 20/2

    • Εισαγωγή-διαδικαστικά. 
    • Προσεγγιστικοί αλγόριθμοι: εισαγωγικές έννοιες, λόγος προσέγγισης, το πρόβλημα Vertex Cover. Το πρόβλημα Set Cover χωρίς βάρη, ανάλυση του Greedy αλγορίθμου (λογαριθμικός λόγος προσέγγισης)  (slides: 1-17)
    • Προσοχή: οι διαφάνειες δεν είναι τελικές, θα ανέβει νεώτερη έκδοση σύντομα.
    • Προτεινόμενη μελέτη: Vazirani κεφ. 1 (κυρίως 1.1), 2.1 και 2.2. Επίσης: DPV 9.2.1.