Διδάσκων: Επίκουρος Καθηγητής Ιωάννης Καραγιάννης, e-mail: caragian@ceid.upatras.gr

Περιγραφή μαθήματος


Αντικείμενο του μαθήματος είναι ο σχεδιασμός και η ανάλυση προσεγγιστικών αλγορίθμων για NP-δύσκολα προβλήματα. Ένας προσεγγιστικός αλγόριθμος παράγει, σε πολυωνυμικό χρόνο, μια λύση η οποία είναι σχετικά κοντά στη βέλτιστη δυνατή. Η αποδοτικότητα ενός τέτοιου αλγορίθμου μετριέται με τον λόγο προσέγγισης.

Περιεχόμενα του μαθήματος


  • Συνδυαστικοί αλγόριθμοι
    • Vertex Cover και Set Cover
    • Steiner Tree και Metric-TSP
    • Knapsack και Bin Packing
    • Minimum makespan scheduling
  • Αλγόριθμοι βασιζόμενοι σε γραμμικό προγραμματισμό
    • Εισαγωγή σε γραμμικό προγραμματισμό
    • Τεχνική dual fitting (Set Cover)
    • Τεχνική randomized rounding (MAX-SAT)
    • Τεχνική primal-dual (Multicut και Integer Multicommodity flow σε δένδρα)

Ενδεικτική βιβλιογραφία


  • Vijay V. Vazirani. Αpproximation algorithms. Springer Verlag, 2001. Μπορείτε να το βρείτε εδώ.
  • David P. Williamson and David B. Shmoys. The design of approximation algorithms. Cambridge Press, 2010. Μπορείτε να το βρείτε εδώ.
Ανάπτυξη ιστοσελίδας: Αλέξανδρος ΒουδούρηςΓεώργιος Κριμπάς