Αλγόριθμοι Δικτύων και Πολυπλοκότητα
Section outline
-
Ακαδ. έτος
- 2017-18
Διδάσκων
- Άρης Παγουρτζής, Αν. Καθηγητής (pagour@cs.ntua.gr)
Βοηθοί διδασκαλίας
- Γιάννης Παπαϊωάννου, Υ.Δ. (ipapaioannou@corelab.ntua.gr)
- Βασίλης Μαργώνης, Υ.Δ. (basilis.math@gmail.com)
Έναρξη μαθήματος
- Το πρώτο μάθημα θα γίνει στις 20/2/2018.
Διαλέξεις
- Παρασκευή 15:00-19:00 Παλιό Κτήριο Ηλεκτρολόγων ΕΜΠ, αίθουσα 1.1.31. (Προσοχή: αλλαγή ημέρας και ώρας!)
Περιεχόμενο μαθήματος (ενδεικτικό)
Το αντικείμενο του μαθήματος είναι η μελέτη αλγοριθμικών μεθόδων και η ανάλυση πολυπλοκότητας για υπολογιστικά προβλήματα και θεμελιώδεις διαδικασίες που σχετίζονται με δίκτυα, κυρίως υπολογιστών και επικοινωνιών. Ορισμένα από τα θέματα που θα καλυφθούν:
- Αποδοτικοί αλγόριθμοι (ακριβείς, προσεγγιστικοί, πιθανοτικοί) για γραφοθεωρητικά προβλήματα βελτιστοποίησης δικτύων: Vertex Cover, Traveling Salesman Problem, Steiner tree, Maximum Flow, Matching, Edge Coloring, Multicommodity Flow, Facility Location, Multicut, k-Center, Clustering, Scheduling.
- Κατανεμημένα πρωτόκολλα: εκλογή αρχηγού, broadcasting, gossiping, byzantine agreement, secret sharing. Ασύρματα ad hoc δίκτυα. Συγχρονισμένοι και ασύγχρονοι αλγόριθμοι. Fault tolerance.
- Προβλήματα αυτόνομων οντοτήτων, εξερεύνηση δικτύων, προβλήματα συνάντησης (rendezvous), εντοπισμός βλαβών σε δίκτυα. Πρωτόκολλα δρομολόγησης, compact routing, geometric routing.
- Ειδικά θέματα: χρονοδρομολόγηση (scheduling), δρομολόγηση και ανάθεση συχνοτήτων σε οπτικά δίκτυα, αλγόριθμοι πλοήγησης, προγραμματισμός δρομολογίων οχημάτων.
- Στοιχεία θεωρίας παιγνίων: σημεία ισορροπίας Nash, "κόστος της αναρχίας". Εγωιστική δρομολόγηση σε κλασικά, ασύρματα και οπτικά δίκτυα. Παίγνια συμφόρησης. Σύγκλιση σε ισορροπίες Nash και σχεδίαση μηχανισμών.
Βιβλιογραφία
- 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.
- H. Karloff. Linear Programming. Birkhäuser, 1991.
- 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.
- Tim Roughgarden. Algorithmic Game Theory. Stanford University Cource, Fall 2013.
- Dorit S. Hochbaum. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997.
-
20/2
- Εισαγωγή: υπενθύμιση βασικών εννοιών αλγορίθμων, πολυπλοκότητας και θεωρίας γραφημάτων.
- Προσεγγιστικοί αλγόριθμοι: εισαγωγικές έννοιες, λόγος προσέγγισης, το πρόβλημα Vertex Cover (slides: 1-15).
Προτεινόμενη μελέτη: Vazirani κεφ. 1 (κυρίως 1.1), και 2.2. Επίσης: DPV 9.2.1.
Προσοχή: οι διαφάνειες δεν είναι τελικές, θα ανέβει νεώτερη έκδοση σύντομα.
-
27/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).
-
9/3
- Προσεγγιστικοί αλγόριθμοι (slides 27-41):
το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem),
μη-προσεγγισιμότητα του γενικού προβλήματος και προσεγγισιμότητα του
Metric TSP. Αλγόριθμος Χριστοφίδη. Το πρόβλημα Steiner Tree. Τα
προβλήματα Mutiway Cut και Minimum k-Cut.
Προτεινόμενη μελέτη: Vazirani 3 και 4, και DPV 9.2.3.
Προσοχή: οι διαφάνειες δεν είναι τελικές, θα ανέβει νεώτερη έκδοση σύντομα.
- Προσεγγιστικοί αλγόριθμοι (slides 27-41):
το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem),
μη-προσεγγισιμότητα του γενικού προβλήματος και προσεγγισιμότητα του
Metric TSP. Αλγόριθμος Χριστοφίδη. Το πρόβλημα Steiner Tree. Τα
προβλήματα Mutiway Cut και Minimum k-Cut.
-
16/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.
-
23/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.
-
30/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.
- Γραμμικός προγραμματισμός: ο αλγόριθμος Simplex (διαφ. 13-26).
-
Διακοπές Πάσχα
-
20/4
- Εισαγωγή στην δυϊκότητα. Πρωτεύον και δυϊκό πρόγραμμα. Ασθενής και ισχυρή δυϊκότητα. Complementary slackness conditions.
Προτεινόμενη μελέτη: Vazirani κεφ. 12.
- Εισαγωγή στην δυϊκότητα. Πρωτεύον και δυϊκό πρόγραμμα. Ασθενής και ισχυρή δυϊκότητα. Complementary slackness conditions.
-
27/4
- Γραμμικός προγραμματισμός για προσεγγιστικούς αλγορίθμους: η μέθοδος Dual Fitting για το πρόβλημα Set Cover (διαφ. 1-9).
Προτεινόμενη μελέτη: Vazirani κεφ. 13.1. - Γραμμικός προγραμματισμός για προσεγγιστικούς αλγορίθμους: μέθοδοι Rounding και Primal-Dual Schema (διαφ. 16-33).
Προτεινόμενη μελέτη: Vazirani κεφ. 14, 15.
- Γραμμικός προγραμματισμός για προσεγγιστικούς αλγορίθμους: η μέθοδος Dual Fitting για το πρόβλημα Set Cover (διαφ. 1-9).
-
4/5
Δεν έγινε μάθημα.
-
11/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].
-
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: διαφάνειες.
- Κατανεμημένοι αλγόριθμοι για προβλήματα δένδρων: διαφάνειες (από μάθημα R. Wattenhofer, slides Stefan Scmhid, ETH Zuerich).
-
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)