Πληροφορίες μαθήματος

Προβλήματα βελτιστοποίησης, κυρτότητα και βελτιστοποίηση. Γραμμικός προγραμματισμός, γεωμετρία, βασικές εφικτές λύσεις, η μέθοδος Simplex, δυϊκότητα, συνθήκες complementary slackness, εφαρμογές θεωρήματος ισχυρής δυϊκότητας. Προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, κάλυμμα κορυφών, κάλυμμα συνόλων, το Πρόβλημα του Πλανόδιου Πωλητή σε μετρικούς χώρους, μη-προσεγγισιμότητα, προβλήματα δρομολόγησης, σχήματα προσέγγισης, το πρόβλημα του σακιδίου. Πιθανοτικοί αλγόριθμοι, παραδείγματα και βασικά εργαλεία από τη θεωρία πιθανοτήτων, ελάχιστη τομή, τυχαία διανομή αντικειμένων σε υποδοχές και εφαρμογές σε εξισορρόπηση φορτίου, φράγματα Chernoff-Hoeffding, τυχαία δειγματοληψία, πιθανοτική μέθοδος, τεχνικές αραίωσης. Αλγοριθμική θεωρία παιγνίων, βασικές έννοιες, ισορροπία Nash, παίγνια συμφόρησης, συναρτήσεις δυναμικού και σύγκλιση σε ισορροπία, τίμημα της αναρχίας. Κοινωνική επιλογή, σχεδιασμός μηχανισμών, ευσταθή ταιριάσματα, δημοπρασίες, βέλτιστη δημοπρασία Myerson, δημοπρασία VCG. Άμεσοι αλγόριθμοι, το πρόβλημα της σελιδοποίησης και το πρόβλημα των k-εξυπηρετητών, προβλήματα δρομολόγησης και εξισορρόπησης φορτίου. Παραμετρικοί αλγόριθμοι και πολυπλοκότητα. Η κλάση FPT. Παραμετρικοί αλγόριθμοι για το πρόβλημα καλύμματος κορυφών. Πυρηνοποίηση (kernelization). Δενδροπλάτος (treewidth). Η W-ιεραρχία. Αναγωγές FPT και W[1]-δυσκολία. Κατανεμημένοι αλγόριθμοι, για προβλήματα δένδρων, εκλογής αρχηγού και χρωματισμών. Αλγόριθμοι και πρωτόκολλα κατανεμημένων ασύρματων δικτύων. Αξιόπιστη εκπομπή, Βυζαντινά πρωτόκολλα, consensus. Αλγόριθμοι κινητών οντοτήτων (mobile agents).