Εθνικό Μετσόβιο Πολυτεχνείο Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών Τομέας Τεχνολογίας Πληροφορικής και Υπολογιστών Προηγμένα Θέματα Αλγορίθμων http://www.softlab.ntua.gr/~fotakis/advanced_algorithms

Προηγμένα Θέματα Αλγορίθμων

Μάθημα Επιλογής Ροής Λ, 8ου Εξαμήνου, Κωδικός 3.4.39.8

Ανακοινώσεις, Γενικά, Περιεχόμενα, Βιβλιογραφία, Γραπτές Εργασίες, Διαλέξεις - Διαφάνειες,

Διαλέξεις: 6/3 | 13/3 | 20/3 | 27/3 | 3/4 | 24/4 | 8/5 | 15/5 | 16/5 | 22/5 | 29/5 | 12/6 

Ανακοινώσεις

Γενικά

• Ώρες γραφείου διδάσκοντα::

  • Δ. Φωτάκης: Δευτέρα 15:00 - 16:00, στο (παλαιό) Κτήριο Ηλεκτρολόγων, γρ. 1.1.10, τηλ. 210-772-4302.

Περιεχόμενα

• Βασικές έννοιες γραμμικού προγραμματισμού, η μέθοδος Simplex, δυϊκότητα στον γραμμικό προγραμματισμό, complementary slackness.
• Πιθανοτικοί αλγόριθμοι, παραδείγματα και βασικά εργαλεία, ελάχιστη τομή, balls and bins και εφαρμογές σε εξισορρόπηση φορτίου, φράγματα Chernoff-Hoeffding, τυχαία δειγματοληψία, πιθανοτική μέθοδος, τεχνικές sparsification.
• Προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, Vertex Cover, Set Cover, TSP σε μετρικούς χώρους, μη-προσεγγισιμότητα, προβλήματα δρομολόγησης, PTAS και FPTAS, Knapsack.
• Προσεγγιστικοί αλγόριθμοι βασισμένοι σε γραμμικό προγραμματισμό, στρογγυλοποίηση, τυχαία στρογγυλοποίηση, η μέθοδος primal-dual.
• Αλγοριθμική θεωρία παιγνίων, βασικές έννοιες, ισορροπία Nash, παίγνια συμφόρησης, συναρτήσεις δυναμικού και σύγκλιση σε ισορροπία, τίμημα της αναρχίας.
• Σχεδιασμός μηχανισμών, κοινωνική επιλογή, ευσταθή ταιριάσματα, δημοπρασίες, βέλτιστη δημοπρασία Myerson, VCG.

Βιβλιογραφία

• Φ. Αφράτη, Γ. Παπαγεωργίου, Τ. Ασλανίδης, Αλγόριθμοι: Μέθοδοι σχεδίασης και ανάλυση πολυπλοκότητας, Εκδόσεις Συμμετρία, Αθήνα (1993).
• K. Steiglitz and C.H. Papadimitriou. Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, 1982.
• 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.
• D.P. Williamson and D.B. Shmoys. The Design of Approximation Algorithms. Cambridge University Press, 2010.
• V.V. Vazirani, Approximation Algorithms, Springer Verlag, Heidelberg, 2001.
• R. Ahuja, T.L. Magnanti and J.B. Orlin. Network Flows: Theory, Algorithms, and Applications. Pearson, 1993.
• 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.

Γραπτές Εργασίες

• Εκφώνηση της 1ης γραπτής εργασίας. Παράδοση εργασιών μέχρι και την Παρασκευή 28/4.
• Εκφώνηση της 2ης γραπτής εργασίας. Παράδοση εργασιών μέχρι και την Πέμπτη 25/5.
• Εκφώνηση της 3ης γραπτής εργασίας. Παράδοση εργασιών στην εξέταση της Τετάρτης 21/6.

Διαλέξεις - Διαφάνειες

Παράδοση 6/3/2017

• Διαδικαστικά θέματα, εισαγωγή.
• Γραμμικός προγραμματισμός: γεωμετρία και βασικές έννοιες.

Παράδοση 13/3/2017

• Η μέθοδος Simplex.
• Δυϊκότητα στον γραμμικό προγραμματισμό

Παράδοση 20/3/2017

• Προσεγγιστικοί Αλγόριθμοι: Vertex Cover, metric TSP, list scheduling (WS 2.3 και 2.4, Vazirani 1, 3.2, και 10.1)

Παράδοση 27/3/2017

• Προσεγγιστικοί Αλγόριθμοι: Set Cover, PTAS και FPTAS, Knapsack, k-Center (WS 1.6, 3.1, και 2.2, Vazirani  2.1, 8 και 5).

Παράδοση 3/4/2017

• Πιθανότητες και Αλγόριθμοι (MU: κεφ. 1, ενότ 2.1-2.4, ενοτ. 3.1-3.3, 5.1., 5.2.1).

Παράδοση 24/4/2017

• Πιθανότητες και Αλγόριθμοι: Πιθανοτικοί αλγόριθμοι για 2-SAT και 3-SAT, Chernoff-Hoeffding bounds (MU: ενοτ. 4.1, 4.2, 4.4, 6.2, 7.1.1, 7.1.2)

Παράδοση 8/5/2017

• Πιθανότητες και Αλγόριθμοι: κάποιες εφαρμογές των Chernoff-Hoeffding bounds, τυχαία δειγματολήψια, secretary problem, prophet inequalities.
• Προσεγγιστικοί Αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό (WS: 1.7, 5.1, 5.4, 5.5).

Παράδοση 15/5/2017

• Προσεγγιστικοί Αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό (WS: 1.4, 1.5, για την primal-dual μέθοδο, αξίζει να δείτε τις ενότητες 7.1 - 7.6, τις οποίες δεν καλύψαμε στο μάθημα).
• Εισαγωγή στην Αλγοριθμική Θεωρία Παιγνίων: ισορροπίες Nash, παίγνια 2-παικτών μηδενικού αθροίσματος, τίμημα της αναρχίας.

Παράδοση 16/5/2017

• Ισορροπίες Nash σε παίγνια δύο-παικτών (δομή και πολυπλοκότητα), λήμμα Sperner, η κλάση PPAD (δείτε και εδώ), μη κατασκευαστικές αποδείξεις ύπαρξης, υπολογισμός προσεγγιστικών ισορροπιών Nash. Μπορείτε ακόμη να δείτε τις ενότητες 1.1, 1.2, 1.3, 2.1, 2.2, και 2.4 από το NRTV.

Παράδοση 22/5/2017

• Κοινωνική επιλογή και κανόνες ψηφοφορίας.
• Σχεδιασμός μηχανισμών (δείτε ακόμη τις σχετικές ενότητες εδώ καθώς και μια ομιλία του Al Roth για kidney exchange). Μπορείτε ακόμη να δείτε τις ενότητες 9.1-9.5 και το κεφάλαιο 10 από το NRTV.

Παράδοση 29/5/2017

• Παίγνια συμφόρησης και ιδιοτελής ανάθεση πόρων. Μπορείτε ακόμη να δείτε τα κεφάλαια 17, 18 και 20 από το NRTV.
• Προβλήματα χρονοδρομολόγησης.

Παράδοση 12/6/2017

• Προβλήματα χρονοδρομολόγησης. Ο αλγόριθμος Miller-Rabin για έλεγχο πρώτων αριθμών.