Section outline

  • 28/2
    • Προσεγγιστικοί αλγόριθμοι: το πρόβλημα Set Cover, χωρίς και με βάρη, f-προσεγγιστικός και H_n-προσεγγιστικός αλγόριθμος. Το πρόβλημα μεγιστοποίησης Maximum Coverage (slides: 16-26).
      Προτεινόμενη μελέτη: Vazirani 2.1 (δείτε και άσκηση 2.15, επίσης την ενότητα 2.3 για μια ενδιαφέρουσα εφαρμογή), και DPV 5.4.