Προηγμένα Θέματα Αλγορίθμων
Weekly outline
- Γενικά
Γενικά
Διδάσκοντες
- Δημήτρης Φωτάκης, Αναπλ. Καθηγητής ( fotakis@cs.ntua.gr )
- Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)
Βοηθοί Διδασκαλίας- Γιάννης Παπαϊωάννου, Υ.Δ.
- Παναγιώτης Πατσιλινάκος, Υ.Δ.
Διαλέξεις
- Κάθε Τετάρτη 16:00 – 19:00, μέσω Webex, στο link: https://centralntua.webex.com/centralntua/j.php?MTID=md0926d1a7577acbda61311c481956ee2
Οι διαλέξεις θα ξεκινήσουν την Τετάρτη 24 Φεβρουαρίου, 2021.
Περιεχόμενα- Προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, Vertex Cover, Set Cover, TSP σε μετρικούς χώρους, μη-προσεγγισιμότητα, προβλήματα δρομολόγησης, PTAS και FPTAS, Knapsack.
- Βασικές έννοιες γραμμικού προγραμματισμού, η μέθοδος Simplex, δυϊκότητα στον γραμμικό προγραμματισμό, complementary slackness.
- Προσεγγιστικοί αλγόριθμοι βασισμένοι σε γραμμικό προγραμματισμό, στρογγυλοποίηση, τυχαία στρογγυλοποίηση, η μέθοδος primal-dual.
- Πιθανοτικοί αλγόριθμοι, παραδείγματα και βασικά εργαλεία, ελάχιστη τομή, balls and bins και εφαρμογές σε εξισορρόπηση φορτίου, φράγματα Chernoff-Hoeffding, τυχαία δειγματοληψία, πιθανοτική μέθοδος, τεχνικές sparsification.
- Αλγοριθμική θεωρία παιγνίων, βασικές έννοιες, ισορροπία Nash, παίγνια συμφόρησης, συναρτήσεις δυναμικού και σύγκλιση σε ισορροπία, τίμημα της αναρχίας.
- Σχεδιασμός μηχανισμών, κοινωνική επιλογή, ευσταθή ταιριάσματα, δημοπρασίες, βέλτιστη δημοπρασία Myerson, VCG.
- Αλγόριθμοι μάθησης, no-regret, multiplicative updates, regression, kNN, SVMs.
- Παραμετρικοί αλγόριθμοι και πολυπλοκότητα.
- Κατανεμημένοι αλγόριθμοι, αξιόπιστη εκπομπή, Βυζαντινά πρωτόκολλα, consensus. Αλγόριθμοι κινητών οντοτήτων (mobile agents).
Βιβλιογραφία
- V.V. Vazirani. Approximation Algorithms. Springer Verlag, Heidelberg, 2001.
- D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge UP, 2010.
- S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms. MacGraw-Hill, 2006.
- K. Steiglitz and C.H. Papadimitriou. Combinatorial Optimization: Algorithms and Complexity.
- V. Chvatal. Linear Programming. W.H. Freeman and Co., 1984.
- H. Karloff. Linear Programming. Birkhäuser, 1991.
- D.G. Luenberger and Y. Ye. Linear and Nonlinear Programming. Springer, 2008.
- R. Ahuja, T.L. Magnanti and J.B. Orlin. Network Flows: Theory, Algorithms, and Applications, 1993.
- N. Lynch, Distributed Algorithms. Morgan Kaufmann Publishers,1996.
- Roger Wattenhofer. Principles of Distributed Computing. ETH Zuerich course notes, 2011.
- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
- M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005.
- N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
- Tim Roughgarden. Algorithmic Game Theory. Stanford University Cource, Fall 2013.
- Ε. Ζάχος, Α. Παγουρτζής, Π. Γροντάς. Υπολογιστική Κρυπτογραφία. Κάλλιπος 2015.
- M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh. Parameterized Algorithms. Springer, 2016.
- 22 February - 28 February
22 February - 28 February
Διάλεξη 24/2: Γραμμικός Προγραμματισμός, Simplex- Εισαγωγή - Διαδικαστικά.
- Τοπική αναζήτηση για προβήματα κυρτής βελτιστοποίησης (δείτε αυτές τις σημειώσεις μέχρι και την ενότητα 2.3), γραμμικός προγραμματισμός, γεωμετρία.
Βίντεο της διάλεξης(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
- 1 March - 7 March
1 March - 7 March
Διάλεξη 3/3: Γραμμικός Προγραμματισμός, η μέθοδος Simplex- Γραμμικός προγραμματισμός, γεωμετρία, κορυφές και βασικές εφικτές λύσεις, η μέθοδος Simplex.
Προτεινόμενη μελέτη: σημειώσεις M. Goemans, μονογραφία H. Karloff, διαφάνειες Π. Σπυράκη.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
- 8 March - 14 March
8 March - 14 March
Διάλεξη 10/3: Δυϊκότητα στον Γραμμικό ΠρογραμματισμόΠροτεινόμενη Μελέτη:
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
- 15 March - 21 March
15 March - 21 March
Διάλεξη 17/3: Προσεγγιστικοί αλγόριθμοι Ι
- Εισαγωγή στους προσεγγιστικούς αλγορίθμους. Το πρόβλημα Vertex Cover με και χωρίς βάρη, 2-προσεγγιστικοί αλγόριθμοι. Ανελαστικά φράγματα (tight bounds). Το πρόβλημα Set Cover: λόγος προσέγγισης του άπληστου αλγόριθμου (Greedy).
Διαφάνειες (προσωρινή έκδοση): 1-30.
Προτεινόμενη μελέτη: Vazirani κεφ. 1 (κυρίως 1.1), 2.1 και 2.2. Επίσης: DPV 9.2.1.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό και ισχύουν περιορισμοί χρήσης, δείτε παραπάνω)
- 22 March - 28 March
22 March - 28 March
Διάλεξη 24/3: Προσεγγιστικοί αλγόριθμοι ΙΙ
- Weighted Set Cover: απόδειξη του λόγου Hn του άπληστου αλγόριθμου. Το
πρόβλημα Maximum Coverage. Το Πρόβλημα Πλανόδιου Πωλητή (Traveling
Salesman Problem), μη-προσεγγισιμότητα του γενικού προβλήματος. 2-προσεγγιστικός αλγόριθμος για το Metric TSP.
Διαφάνειες: 31-45.
Προτεινόμενη μελέτη: Vazirani άσκηση 2.15 (δείτε επίσης την ενότητα 2.3 για μια ενδιαφέρουσα εφαρμογή) και 3.2, και DPV 5.4, 9.2.3
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό και ισχύουν περιορισμοί χρήσης, δείτε παραπάνω) - Weighted Set Cover: απόδειξη του λόγου Hn του άπληστου αλγόριθμου. Το
πρόβλημα Maximum Coverage. Το Πρόβλημα Πλανόδιου Πωλητή (Traveling
Salesman Problem), μη-προσεγγισιμότητα του γενικού προβλήματος. 2-προσεγγιστικός αλγόριθμος για το Metric TSP.
- 29 March - 4 April
29 March - 4 April
Διάλεξη 31/3: Προσεγγιστικοί αλγόριθμοι ΙΙΙ
- Αλγόριθμος Χριστοφίδη για το Metric TSP. Αλγόριθμος Hoogeveen για το πρόβλημα TSP(s-t path).
- Το πρόβλημα Steiner Tree και Metric Steiner Tree. Αναγωγές
διατήρησης προσέγγισης.
- Τα προβλήματα Mutiway Cut και Minimum k-Cut.
Διαφάνειες: 46-58.
Προτεινόμενη μελέτη: Vazirani κεφ. 3.1 και 4.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό, και ισχύουν περιορισμοί χρήσης, δείτε παραπάνω)
- Αλγόριθμος Χριστοφίδη για το Metric TSP. Αλγόριθμος Hoogeveen για το πρόβλημα TSP(s-t path).
- 5 April - 11 April
5 April - 11 April
Διάλεξη 7/4: Προσεγγιστικοί αλγόριθμοι IV
- Προσεγγιστικοί αλγόριθμοι (2η ενότητα, slides 25-34):
ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά
σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα
(Discrete) Knapsack.
Προτεινόμενη μελέτη: Vazirani κεφ. 8. - Προσεγγιστικοί αλγόριθμοι (3η ενότητα):
το πρόβλημα Minimum Makespan Scheduling. Ισχυρή NP-πληρότητα (αναγωγή
από 3-PARTITION) και προσεγγιστικοί αλγόριθμοι: 2-προσεγγιστικός,
(4/3)-προσεγγιστικός, PTAS.
Προτεινόμενη μελέτη: Vazirani κεφ. 10.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό, και ισχύουν περιορισμοί χρήσης, δείτε παραπάνω) - Προσεγγιστικοί αλγόριθμοι (2η ενότητα, slides 25-34):
ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά
σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα
(Discrete) Knapsack.
- 12 April - 18 April
12 April - 18 April
Διάλεξη 14/4: Πιθανοτικοί Αλγόριθμοι Ι
- Πιθανοτικοί αλγόριθμοι, ο αλγόριθμος του Karger για το πρόβλημα της Ελάχιστης Τομής, balls and bins, coupons collector, η πιθανοτική μέθοδος (απλά παραδείγματα εφαρμογής σε max-cut και maximum independent set).
Προτεινόμενη μελέτη:- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. (κεφάλαιο 1 και ενότητες 10.2, 3.1, 3.2, 3.6, 5.1, 5.2 και 5.5).
- M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. (κεφάλαια 1 και 2, και ενότητες 3.1-3.3, 6.1, 6.2, 6.4 και 6.7).
Προτάσεις για περαιτέρω μελέτη:- Martin Aigner and Günter M. Ziegler. Proofs from THE BOOK (6th edition). Springer, 2018.
- Noga Alon Joel and H. Spencer. The Probabilistic Method. Wiley, 2008. Παλαιότερη έκδοση.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).