Προηγμένα Θέματα Αλγορίθμων
Weekly outline
- Γενικά
Γενικά
Ακαδ. έτος
- 2017-18
Διδάσκοντες
- Άρης Παγουρτζής, Αναπληρωτής Καθηγητής (pagour@cs.ntua.gr)
- Δημήτριος Φωτάκης, Επίκουρος Καθηγητής (fotakis@cs.ntua.gr)
Βοηθοί Διδασκαλίας- Στρατής Σκουλάκης, Υ.Δ. (stratis.skoulakis@gmail.com)
- Βασίλης Κοντονής (vkonton@gmail.com)
Βοηθοί Ασκήσεων
- Ευαγγελία Γεργατσούλη
- Αλέξανδρος Τσιγώνιας
Διαλέξεις
- Τετάρτη 15:15 – 18:00, Αίθoυσα 009, Νέα Κτήρια ΗΜΜΥ
Περιεχόμενα- Προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, Vertex Cover, Set Cover, TSP σε μετρικούς χώρους, μη-προσεγγισιμότητα, προβλήματα δρομολόγησης, PTAS και FPTAS, Knapsack.
- Βασικές έννοιες γραμμικού προγραμματισμού, η μέθοδος Simplex, δυϊκότητα στον γραμμικό προγραμματισμό, complementary slackness.
- Προσεγγιστικοί αλγόριθμοι βασισμένοι σε γραμμικό προγραμματισμό, στρογγυλοποίηση, τυχαία στρογγυλοποίηση, η μέθοδος primal-dual.
- Πιθανοτικοί αλγόριθμοι, παραδείγματα και βασικά εργαλεία, ελάχιστη τομή, balls and bins και εφαρμογές σε εξισορρόπηση φορτίου, φράγματα Chernoff-Hoeffding, τυχαία δειγματοληψία, πιθανοτική μέθοδος, τεχνικές sparsification.
- Αλγοριθμική θεωρία παιγνίων, βασικές έννοιες, ισορροπία Nash, παίγνια συμφόρησης, συναρτήσεις δυναμικού και σύγκλιση σε ισορροπία, τίμημα της αναρχίας.
- Σχεδιασμός μηχανισμών, κοινωνική επιλογή, ευσταθή ταιριάσματα, δημοπρασίες, βέλτιστη δημοπρασία Myerson, VCG.
Βιβλιογραφία
- 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.
- 19 February - 25 February
19 February - 25 February
21/2
- Υπενθύμιση βασικών εννοιών πολυπλοκότητας (κλάσεις, αναγωγές, NP-πληρότητα).
- Εισαγωγή-διαδικαστικά.
- Προσεγγιστικοί αλγόριθμοι: εισαγωγικές έννοιες, λόγος προσέγγισης, το πρόβλημα Vertex Cover (slides: 1-15).
Προτεινόμενη μελέτη: Vazirani κεφ. 1 (κυρίως 1.1), και 2.2. Επίσης: DPV 9.2.1.
- Υπενθύμιση βασικών εννοιών πολυπλοκότητας (κλάσεις, αναγωγές, NP-πληρότητα).
- 26 February - 4 March
26 February - 4 March
28/2
- Προσεγγιστικοί αλγόριθμοι: το πρόβλημα Set Cover, χωρίς και με βάρη, f-προσεγγιστικός και H_n-προσεγγιστικός αλγόριθμος. Το πρόβλημα μεγιστοποίησης Maximum Coverage (slides: 16-26).
Προτεινόμενη μελέτη: Vazirani 2.1 (δείτε και άσκηση 2.15, επίσης την ενότητα 2.3 για μια ενδιαφέρουσα εφαρμογή), και DPV 5.4.
- Προσεγγιστικοί αλγόριθμοι: το πρόβλημα Set Cover, χωρίς και με βάρη, f-προσεγγιστικός και H_n-προσεγγιστικός αλγόριθμος. Το πρόβλημα μεγιστοποίησης Maximum Coverage (slides: 16-26).
- 5 March - 11 March
5 March - 11 March
7/3
- Προσεγγιστικοί αλγόριθμοι (slides 27-43):
το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem), μη-προσεγγισιμότητα του γενικού προβλήματος και προσεγγισιμότητα του Metric TSP. Αλγόριθμος Χριστοφίδη. Το πρόβλημα Steiner Tree. Τα προβλήματα Mutiway Cut και Minimum k-Cut.
Προτεινόμενη μελέτη: Vazirani 3 και 4, και DPV 9.2.3.
- Προσεγγιστικοί αλγόριθμοι (slides 27-43):
το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem), μη-προσεγγισιμότητα του γενικού προβλήματος και προσεγγισιμότητα του Metric TSP. Αλγόριθμος Χριστοφίδη. Το πρόβλημα Steiner Tree. Τα προβλήματα Mutiway Cut και Minimum k-Cut.
- 12 March - 18 March
12 March - 18 March
14/3
- Προσεγγιστικοί αλγόριθμοι (2η ενότητα, slides 25-34): ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα (Discrete) Knapsack.
- Προσεγγιστικοί αλγόριθμοι (3η ενότητα): το πρόβλημα Minimum Makespan Scheduling. Ισχυρή NP-πληρότητα (αναγωγή από 3-PARTITION) και προσεγγιστικοί αλγόριθμοι: 2-προσεγγιστικός, (4/3)-προσεγγιστικός, PTAS.
- Προτεινόμενη μελέτη: Vazirani κεφ. 8 και 10.
- 19 March - 25 March
19 March - 25 March
21/3
- Προσεγγιστικοί αλγόριθμοι (3η ενότητα): προσεγγιστικό σχήμα (PTAS) για το πρόβλημα Minimum Makespan Scheduling με αναγωγή στο Restricted Bin Packing. Ακριβής αλγόριθμος δυναμικού προγραμματισμού για το Restricted Bin Packing.
Προτεινόμενη μελέτη: Vazirani κεφ. 10.
- Γραμμικός προγραμματισμός: εισαγωγή, τυπική και κανονική μορφή, πολύεδρο εφικτών λύσεων, βασικές εφικτές λύσεις (διαφ. 1-12).
(ανέβηκε νέα έκδοση).
Προτεινόμενη μελέτη: DPV 7.1 (δείτε και Karloff κεφ. 1 για μια πιο αναλυτική παρουσίαση, καθώς και τις πολύ καλές διαφάνειες/σημειώσεις του μαθήματος LP του Henry Wolkowicz, U Waterloo, ενότητες 1-4 και 11-13).
- Προσεγγιστικοί αλγόριθμοι (3η ενότητα): προσεγγιστικό σχήμα (PTAS) για το πρόβλημα Minimum Makespan Scheduling με αναγωγή στο Restricted Bin Packing. Ακριβής αλγόριθμος δυναμικού προγραμματισμού για το Restricted Bin Packing.
- 26 March - 1 April
26 March - 1 April
28/3
- Γραμμικός προγραμματισμός: ο αλγόριθμος Simplex (διαφ. 13-26).
Προτεινόμενη μελέτη: Karloff κεφ. 2, δείτε και τις πολύ καλές διαφάνειες/σημειώσειςτου μαθήματος LP του Henry Wolkowicz, U Waterloo, (ενότητες 14-16, αλλά και 17-20 για πιο προχωρημένα θέματα). Δείτε ακόμη DPV 7.6 για έναν διαφορετικό, αλλά αρκετά ενδιαφέροντα τρόπο παρουσίασης του Simplex. - Χρήση γραμμικού προγραμματισμού για προσεγγιστικούς αλγορίθμους, f-προσεγγιστικός αλγόριθμος για το Set Cover με στρογγυλοποίηση (rounding).
Προτεινόμενη μελέτη: Vazirani κεφ. 14.1. - Εισαγωγή στην δυϊκότητα. Πρωτεύον και δυϊκό πρόγραμμα (διαφ. 1-7).
Προτεινόμενη μελέτη: Vazirani κεφ. 12.
- Γραμμικός προγραμματισμός: ο αλγόριθμος Simplex (διαφ. 13-26).
- 2 April - 15 April
- 16 April - 22 April
16 April - 22 April
18/4
- Εισαγωγή στην δυϊκότητα. Πρωτεύον και δυϊκό πρόγραμμα. Ασθενής και ισχυρή δυϊκότητα. Complementary slackness conditions.
Προτεινόμενη μελέτη: Vazirani κεφ. 12. - Γραμμικός προγραμματισμός για προσεγγιστικούς αλγορίθμους: η μέθοδος Dual Fitting για το πρόβλημα Set Cover (διαφ. 1-9).
Προτεινόμενη μελέτη: Vazirani κεφ. 13.1.
- Εισαγωγή στην δυϊκότητα. Πρωτεύον και δυϊκό πρόγραμμα. Ασθενής και ισχυρή δυϊκότητα. Complementary slackness conditions.
- 23 April - 29 April
23 April - 29 April
25/4
- Γραμμικός προγραμματισμός για προσεγγιστικούς αλγορίθμους: μέθοδοι Rounding και Primal-Dual Schema (διαφ. 16-33).
Προτεινόμενη μελέτη: Vazirani κεφ. 14, 15. - Μη προσεγγισιμότητα με χρήση PCP. Το πρόβλημα Max3Sat: δυσκολία προσέγγισης και προσεγγισιμότητα (derandomization με τη μέθοδο των conditional expectations). [Παρουσίαση: Β. Μαργώνης]
- Γραμμικός προγραμματισμός για προσεγγιστικούς αλγορίθμους: μέθοδοι Rounding και Primal-Dual Schema (διαφ. 16-33).
- 30 April - 6 May
30 April - 6 May
2/5
Πιθανοτικοί αλγόριθμοι:
- Πρόβλημα ελάχιστης τομής (mincut - αλγόριθμος του Karger) [MU, 1.5].
- Πρόβλημα μέγιστης τομής (maxcut - πιθανοτική μέθοδος και derandomization) [MU, 6.2 & 6.3].
- Αλγόριθμοι Las Vegas και Monte Carlo (MU, σελ. 62).
- Πιθανοτικό πρωτόκολλο για έλεγχο ισότητας συμβολοσειρών. [R. Karp: Introduction to Randomized Algorithms, Section 5]
[Παρουσίαση: Ν. Λεονάρδος]MU: Mitzenmacher-Upfal, 2nd edition
Δείτε και: https://www.cs.ox.ac.uk/people/elias.koutsoupias/pc2016-17/lectures.pdf (2.2, 3.2)
- Πρόβλημα ελάχιστης τομής (mincut - αλγόριθμος του Karger) [MU, 1.5].
- 7 May - 13 May
7 May - 13 May
9/5
Θεωρία αριθμών. Θεωρία ομάδων. Πιθανοτικοί έλεγχοι πρώτων αριθμών: Fermat test και Miller-Rabin test. Η χρήση του Θ. Lagrange στους πιθανοτικούς αλγορίθμους.
Διαφάνειες set 1: 1-54
Διαφάνειες set 2: 1-8
(προσωρινές, θα γίνουν αλλαγές)
- 14 May - 20 May
14 May - 20 May
18/5
Κατανεμημένοι αλγόριθμοι:
- Κατανεμημένοι αλγόριθμοι για προβλήματα δένδρων: διαφάνειες (από μάθημα R. Wattenhofer, slides Stefan Scmhid, ETH Zuerich).
- Το πρόβλημα εκλογής αρχηγού σε δακτύλιο: διαφάνειες (από μάθημα R. Wattenhofer, slides Stefan Scmhid, ETH Zuerich).
- Κατανεμημένοι αλγόριθμοι χρωματισμού: διαφάνειες (από μάθημα R. Wattenhofer, slides Stefan Scmhid, ETH Zuerich).
- Αλγόριθμοι και πρωτόκολλα κατανεμημένων ασύρματων δικτύων: broadcasting and gossiping in radio networks: διαφάνειες. Σχετική εργασία (M. Chrobak, L. Gasieniec, W. Rytter).
[Παρουσίαση: Ι. Παπαϊωάννου - Α. Παγουρτζής]Προτεινόμενη μελέτη: μάθημα Principles of Distributed Computing, R. Wattenhofer (ETH Zurich): κεφ. 0, 1, 2, 3.
- Κατανεμημένοι αλγόριθμοι για προβλήματα δένδρων: διαφάνειες (από μάθημα R. Wattenhofer, slides Stefan Scmhid, ETH Zuerich).
- 21 May - 27 May
21 May - 27 May
25/5
Παραμετρικοί αλγόριθμοι. Αλγόριθμοι FPT για το Vertex Cover. Πυρηνοποίηση (kernelization). Δενδροπλάτος (treewidth). FPT reductions και W[1]-hardness.
[Παρουσίαση: Ε. Αναστασιάδη]
Προτεινόμενη μελέτη: Fundamentals of Parameterized Complexity, Rodney G. Downey , Michael R. Fellows. (κεφ. 2, 3.1-3.3, 4.2, 10.2, 20, προαιρετικά: 21, 22.2, 22.3)
- 28 May - 3 June
28 May - 3 June
1/6
Παίγνια συμφόρησης, παράδοξο Pigou, παράδοξο Braess. Ισορροπίες Nash / Wardrop. Το Τίμημα της Αναρχίας (Price of Anarchy). Θεώρημα Roughgarden-Tardos.
Τεχνικές εκμάθησης "χωρίς μεταμέλεια" (no-regret learning). Αλγόριθμος Εκτιμώμενων Βαρών (Expected Weights ή Multiplicative Weights). Σύγκλιση παιγνίων συμφόρησης σε σημεία ισορροπίας.[Παρουσίαση: Π. Μερτικόπουλος]Προτεινόμενη μελέτη: Selfish Routing and the Price of Anarchy, No-Regret Dynamics (Διαλέξεις T. Roughgarden, μάθημα Algorithmic Game Theory, Stanford). - 4 June - 10 June