Προηγμένα Θέματα Αλγορίθμων
Section outline
-
Διδάσκοντες
- Δημήτρης Φωτάκης, Αναπλ. Καθηγητής ( fotakis@cs.ntua.gr )
- Άρης Παγουρτζής, Καθηγητής ( pagour@cs.ntua.gr )
- Θανάσης Λιανέας, Μεταδιδακτορικός Ερευνητής ( lianeas@corelab.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.
-
Διάλεξη 24/2: Γραμμικός Προγραμματισμός, Simplex
- Εισαγωγή - Διαδικαστικά.
- Τοπική αναζήτηση για προβήματα κυρτής βελτιστοποίησης (δείτε αυτές τις σημειώσεις μέχρι και την ενότητα 2.3), γραμμικός προγραμματισμός, γεωμετρία.
Βίντεο της διάλεξης(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
-
Διάλεξη 3/3: Γραμμικός Προγραμματισμός, η μέθοδος Simplex
- Γραμμικός προγραμματισμός, γεωμετρία, κορυφές και βασικές εφικτές λύσεις, η μέθοδος Simplex.
Προτεινόμενη μελέτη: σημειώσεις M. Goemans, μονογραφία H. Karloff, διαφάνειες Π. Σπυράκη.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
-
Διάλεξη 10/3: Δυϊκότητα στον Γραμμικό Προγραμματισμό
Προτεινόμενη Μελέτη:
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
-
Διάλεξη 17/3: Προσεγγιστικοί αλγόριθμοι Ι
- Εισαγωγή στους προσεγγιστικούς αλγορίθμους. Το πρόβλημα Vertex Cover με και χωρίς βάρη, 2-προσεγγιστικοί αλγόριθμοι. Ανελαστικά φράγματα (tight bounds). Το πρόβλημα Set Cover: λόγος προσέγγισης του άπληστου αλγόριθμου (Greedy).
Διαφάνειες (προσωρινή έκδοση): 1-30.
Προτεινόμενη μελέτη: Vazirani κεφ. 1 (κυρίως 1.1), 2.1 και 2.2. Επίσης: DPV 9.2.1.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό και ισχύουν περιορισμοί χρήσης, δείτε παραπάνω)
-
Διάλεξη 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.
-
Διάλεξη 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).
-
Διάλεξη 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.
-
Διάλεξη 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).
- 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).
Προτάσεις για περαιτέρω μελέτη:- 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 ή μέσο).
-
Διάλεξη 21/4: Πιθανοτικοί Αλγόριθμοι ΙI
- Πιθανοτικοί αλγόριθμοι: πιθανοτικοί αλγόριθμοι για τα προβλήματα 2-SAT (δείτε και αυτές τις διαφάνειες για το 2-SAT) και 3-SAT (δείτε και αυτές τις διαφάνειες για το 3-SAT), secretary problem, (δείτε ακόμη εδώ για secretary problems), Lovasz Local Lemma και εφαρμογή στην ικανοποιησιμότητα k-SAT, Chernoff-Hoeffding bounds, set balancing.
Προτεινόμενη μελέτη:- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. (ενότητες 4.1, 5.5, 6.1, 6.2 και 6.3).
- M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. (Ενότητες 3.1-3.3, 4.1-4.5, 6.7 και 7.1).
Προτάσεις για περαιτέρω μελέτη:- Thomas S. Ferguson. Who Solved the Secretary Problem? Statist. Sci. 4(3): 282-289, 1989.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
-
Διάλεξη 28/4: Πιθανοτικοί Αλγόριθμοι ΙII - Προσεγγιστικοί Αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό
- Πιθανοτικοί αλγόριθμοι: Chernoff-Hoeffding bounds, set balancing, τυχαία δειγματοληψία.
- Η βασική ιδέα / προσέγγιση του να χρησιμοποιήσουμε Γραμμικό Προγραμματισμό για να σχεδιάσουμε και να αναλύσουμε προσεγγιστικούς αλγόριθμους, ILP formulations και LP relaxations, randomized (και deterministic) rounding για VLSI routing, Set Cover, Max-Cut.
Προτεινόμενη μελέτη:- Διαφάνειες για προσεγγιστικούς αλγόριθμους βασισμένους σε Γραμμικό Προγραμματισμό.
- D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Ενότητες: 1.3-1.7, 5.1-5.2, 5.4-5.5, και 6.1-6.3.
- Σημειώσεις και σημειώσεις για την μέθοδο των conditional expectations (δείτε και το σχετικό λήμμα στο wikipedia).
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
-
Διάλεξη 12/5: Προσεγγιστικοί Αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό (συνέχεια), Βασικές Έννοιες (Αλγοριθμικής) Θεωρίας Παιγνίων
- Max-Cut και Max-SAT, ισχυρότερα relaxations, Semidefinite Programming και o αλγόριθμος Goemans-Williamson για το πρόβλημα MAX-CUT.
- Primal-dual μέθοδος για το πρόβλημα set cover.
- Βασικές έννοιες Θεωρίας Παιγνίων και σύντομη εισαγωγή στην Αλγοριθμική Θεωρία Παιγνίων (διαφάνειες), παραδείγματα παιγνίων, παίγνια 2 παικτών.
Προτεινόμενη μελέτη:- D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2011. Ενότητες: 7.1 - 7.6 (μέθοδος primal-dual για αλγόριθμους προσέγγισης) και 1.6 (η μέθοδος dual fitting για set cover).
- Σημειώσεις για παίγνια μηδενικού αθροίσματος και το θεώρημα του Nash.
- Anna R. Karlin and Yuval Peres. Game Theory, Alive. American Mathematical Society, 2016. Κεφάλαια: 2, 4 και 5.
- Σημειώσεις από το μάθημα του Tim Roughgarden: Σύντομη εισαγωγή στην Αλγοριθμική Θεωρία Παιγνίων.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
- Max-Cut και Max-SAT, ισχυρότερα relaxations, Semidefinite Programming και o αλγόριθμος Goemans-Williamson για το πρόβλημα MAX-CUT.
-
Διάλεξη 19/5: Αλγοριθμική Θεωρία Παιγνίων - Βασικές έννοιες σχεδιασμού μηχανισμών
- Υπολογισμός ισορροπίας σε 2-player zero-sum games, von Neumann Minimax Theorem (διαφάνειες, καλύπτουν περισσότερη ύλη από αυτή που παρουσιάσαμε στο μάθημα).
- Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson.
- Υπολογιστικά αποδοτικοί μηχανισμοί και μονότονοι αλγόριθμοι προσέγγισης.
- Multi-dimensional bidders, complements and substitutes, subadditive, submodular και superadditive valuation functions.
- Social welfare maximization, Walrasian equilibrium, VCG μηχανισμός.
Προτεινόμενη μελέτη:
- Διαφάνειες του κ. Μαρκάκη: 1ο set και 2o set.
- Σημειώσεις από το μάθημα του Tim Roughgarden: Myerson's Lemma και εφαρμογές, VCG μηχανισμός.
- Ενότητες 9.3, 9.5, 11.2, 11.3, 11.5 και 11.7 από βιβλίο σε Algorithmic Game Theory.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
-
Διάλεξη 26/5
Α. Το Πρόβλημα της Ανάθεσης και της Μεταφοράς
Διαφάνειες (όπως παρουσιάστηκαν)
Διαφάνειες (πλήρης έκδοση)Προτεινόμενη μελέτη: Κεφάλαιο 5 από το βιβλίο του H. Taha ή κεφάλαιο 9 από το βιβλίο των F. Hillier and G. Lieberman (υπάρχουν και ελληνικές εκδόσεις) και σημειώσεις (i) για το primal-dual σχήμα και (ii) για ταιριάσματα, καλύμματα, Θεώρημα Konig, TU πίνακες.
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
Β. Πιθανοτικοί αλγόριθμοι στη θεωρία αριθμών και την κρυπτογραφία (Ι)- Θεωρία αριθμών. Διαιρετότητα. Κινέζικο Θεώρημα Υπολοίπων.
- Θεωρία ομάδων. Σύμπλοκα, τάξη ομάδας, γεννήτορες. Θ. Lagrange και χρήση του στους πιθανοτικούς αλγορίθμους.
Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 2.1, 2.2, 2.3, 4.5. Δείτε και: [CLRS, 3rd edition] κεφ. 31 (Number-theoretic Algorithms).(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).
-
Διάλεξη 2/6
Α. Πιθανοτικοί αλγόριθμοι στη θεωρία αριθμών και την κρυπτογραφία (ΙI)
- Οι έλεγχοι πρώτων αριθμών Fermat και Miller-Rabin.
- Αλγόριθμος παραγοντοποίησης Pollard-rho
- Ευεπίλυτα και δυσεπίλυτα αριθμοθεωρητικά προβλήματα
- Διαφάνειες (25-36)
- Προτεινόμενη μελέτη: [ΖΠΓ] κεφ. 4.4, 4.5, 4.6. Δείτε και: [CLRS, 3rd edition] κεφ. 31 (Number-theoretic Algorithms).
Β. Εισαγωγή σε παραμετρικούς αλγορίθμους και πολυπλοκότητα
- Η κλάση FPT. FPT αλγόριθμοι για το Vertex Cover. Πυρηνοποίηση (kernelization).
- Παραμετρικός αλγόριθμος για Independet Set με παράμετρο το treewidth (δενδροπλάτος).
- Αλγόριθμος για 3-Coloring και Θεώρημα Courcelle (απλή αναφορά).
- Παραμετρικές αναγωγές. Παραμετρική δυσκολία των Independent Set, Dominating set. W-hierarchy, weft (απλή αναφορά).
- Διαφάνειες (1-29), Διαφάνειες (1-18) και Διαφάνειες (1-17 συνοπτικά). Δείτε και Διαφάνειες (συμπληρωματικές, 1-7)
- Προτεινόμενη μελέτη: [M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh. Parameterized Algorithms. Springer, 2016.], κεφ. 1, 2.1, 2.2.1, 3.1, 7.1-7.4, και 13.1-13.3 (συνοπτικά, ορισμούς μόνο).
(ΠΡΟΣΟΧΗ: Απαιτείται συνθηματικό για την πρόσβαση. Το υλικό των διαλέξεων προορίζεται αποκλειστικά για προσωπική χρήση των φοιτητών του μαθήματος και δεν επιτρέπεται η ανάρτησή του ή μεταφόρτωσή του σε οποιοδήποτε άλλο site ή μέσο).