Advanced Algorithms

Topic outline

• 

  Γενικά - Ανακοινώσεις - Forum

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

    Εδώ αναρτώνται οι γενικές ανακοινώσεις από τους διδάσκοντες προς τους εγγεγραμμένους φοιτητές, οι οποίοι τις λαμβάνουν και στην ηλεκτρονική τους διεύθυνση.
    
    
  • Forum Ερωτήσεων/Απαντήσεων

    Σε αυτό το forum, μπορεί οποιοσδήποτε εγγεγραμμένος φοιτητής να αναρτά ερωτήσεις σχετικές με το μάθημα και να λαμβάνει απαντήσεις από τους διδάσκοντες. Οι ερωτήσεις και οι απαντήσεις θα είναι διαθέσιμες σε όλους τους φοιτητές. 

    Οι φοιτητές μπορούν να δηλώσουν με την εγγραφή τους αν θέλουν να ενημερώνονται για τις αναρτώμενες ερωταπαντήσεις.

    
    

• 

  Διδάσκοντες / Βοηθοί Διδασκαλίας

  • Άρης Παγουρτζής, Καθηγητής ()
  • Δημήτρης Φωτάκης, Καθηγητής ()
  • Θανάσης Λιανέας, Μεταδιδακτορικός Ερευνητής ()

  
  

  Ώρες Γραφείου Διδασκόντων

  • Άρης Παγουρτζής: Πέμπτη 15:00-16:00, γραφείο 1.1.6, (Παλαιό) Κτήριο Ηλεκτρολόγων.
  • Δημήτρης Φωτάκης: Τετάρτη 14:00 - 15:00, στο γραφείο 1.1.10, (Παλαιό) Κτήριο Ηλεκτρολόγων.
  • Θανάσης Λιανέας: θα ανακοινωθούν.

  
  

  Βοηθοί Διδασκαλίας

  • Άλκης Καλαβάσης
  • Μαριάννα Σπυράκου
• 

  Γενικές Πληροφορίες

  Οι διαλέξεις του μαθήματος γίνονται κάθε Τετάρτη, ώρα 16:15-19:00, στο Νέο Κτήριο Ηλεκτρολόγων, Αίθουσα 009.
  

  Η πρώτη διάλεξη για το εαρινό εξάμηνο 2023 θα γίνει την Τετάρτη 1η Μαρτίου.
  
• 

  Περιεχόμενα

  • Προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, 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 Zurich 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. 
  • Noam Nisan, Tim Roughgarden, Eva Tardos and Vijay V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
    
  • Tim Roughgarden. Twenty Lectures on Algorithmic Game Theory. Cambridge University Press, 2016. Δείτε ακόμη τα lecture notes και τις video-διαλέξεις από παλαιότερο σχετικό μάθημα του Tim Roughgarden. 
    
  • Tim Roughgarden. Complexity Theory, Game Theory, and Economics: The Barbados Lectures. Foundations and Trends in Theoretical Computer Science: Vol. 14: No. 3–4, pp 222-407, now publishers inc., 2020. Δείτε ακόμη εδώ. 
    
  • Anna R. Karlin and Yuval Peres. Game Theory, Alive. American Mathematical Society, 2016. 
  • Ε. Ζάχος, Α. Παγουρτζής, Π. Γροντάς. Υπολογιστική Κρυπτογραφία. Κάλλιπος 2015.
    
  • M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh. Parameterized Algorithms. Springer, 2016.

  
  
• 

  Παλαιότερα Έτη

  • Ιστοσελίδα του μαθήματος για προηγούμενα ακαδημαϊκά έτη: 2021-2022, 2020-2021, 2019-2020, 2018-2019, 2017-2018, 2016-2017.
  • Στην ιστοσελίδα του μαθήματος για το ακαδ. έτος 2020-2021, μπορείτε να βρείτε βιντεοσκοπημένες διαλέξεις. 

  
  
• 

  Εκπαιδευτικό Υλικό / Προτεινόμενη Μελέτη

  • Σημειώσεις με βασικές έννοιες σχετικές με κυρτά σύνολα και κυρτή βελτιστοποίηση. 
  • Σημειώσεις για κυρτή βελτιστοποίηση και για τη μέθοδο gradient descent. 
  • Survey του Avrim Blum για χρήση online αλγορίθμων για μάθηση και σημειώσεις για τους αλγόριθμους weighted majority και randomized weighted majority (και κάποιες επιπλέον σημειώσεις: 1ο μέρος και 2ο μέρος). 
  • Σημειώσεις και διαφάνειες σχετικές με Γραμμικό Προγραμματισμό (γεωμετρία, βασικά θεωρήματα και ιδιότητες, μέθοδος Simplex, δυϊκότητα, εφαρμογές): 
  • Σημειώσεις M. Goemans.
  • Μονογραφία H. Karloff. 
  • Διαφάνειες Π. Σπυράκη. 
  • Σημειώσεις που αναφέρονται στο Λήμμα του Farkas, στη γεωμετρική του ερμηνεία, και στις εφαρμογές του. 
  • Υλικό για πιθανοτικούς αλγόριθμους:
  • Αλγόριθμος του Karger για το πρόβλημα Ελάχιστης Τομής (wikipedia και σημειώσεις). 
  • R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995: κεφάλαιο 1, ενότητες 3.1, 3.2, 3.6, 4.1, 5.1, 5.2, 5.5, 6.1, 6.2, 6.3, 10.2.
  • M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005: κεφάλαια 1 και 2, ενότητες 3.1-3.3, 4.1-4.5, 6.1, 6.2, 6.4, 6.7, 7.1.
  • Βιβλία / υλικό για την πιθανοτική μέθοδο:
  • 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. Παλαιότερη έκδοση. 
  • Σχετικά με το secretary problem:
  • Thomas S. Ferguson. Who Solved the Secretary Problem? Statist. Sci. 4(3): 282-289, 1989.
    
  • Υλικό για προσεγγιστικούς αλγόριθμους βασισμένους σε γραμμικό προγραμματισμό:
  • 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 και 11.1. 

  
  
• 

  Διαλέξεις

  • Διάλεξη 1/3/2023. Εισαγωγή - Διαδικαστικά. Εισαγωγή στους προσεγγιστικούς αλγορίθμους (1-36). Το πρόβλημα Vertex Cover με και χωρίς βάρη, 2-προσεγγιστικοί αλγόριθμοι. Ανελαστικά φράγματα (tight bounds). Το πρόβλημα (Weighted) Set Cover: λόγος προσέγγισης του άπληστου αλγόριθμου (Greedy). Προτεινόμενη μελέτη: Vazirani κεφ. 1, 2.1 και 2.2. Επίσης: DPV 9.2.1 και 5.4.
  • Διάλεξη 22/3/2023. Το πρόβλημα Maximum Coverage. Το Πρόβλημα Πλανόδιου Πωλητή (Traveling Salesman Problem, TSP), μη-προσεγγισιμότητα, αλγόριθμος Χριστοφίδη. Πρόβλημα TSP (s-t path), αλγόριθμος Hoogeveen. Διαφάνειες (37-49). Προτεινόμενη μελέτη: Vazirani 2.1, και άσκηση 2.15 (δείτε επίσης την ενότητα 2.3 για μια ενδιαφέρουσα εφαρμογή). 
  • Διάλεξη 29/3/2023. Τα προβλήματα Steiner Tree και Metric Steiner Tree. Αναγωγές διατήρησης προσέγγισης. Τα προβλήματα Mutiway Cut και Minimum k-Cut. Δένδρα Gomory-Hu. Διαφάνειες (50-59). Προτεινόμενη μελέτη: Vazirani, κεφ. 3 και 4, και DPV 9.2.3.
  • Διάλεξη 5/4/2023. Ψευδοπολυωνυμικοί αλγόριθμοι, ισχυρή NP-πληρότητα, και προσεγγιστικά σχήματα πολυωνυμικού χρόνου (PTAS, FPTAS). FPTAS για το πρόβλημα (Discrete) Knapsack. Διαφάνειες (25-34).  Το πρόβλημα Minimum Makespan Scheduling. Ισχυρή NP-πληρότητα (αναγωγή από 3-PARTITION) και προσεγγιστικοί αλγόριθμοι: 2-προσεγγιστικός, (4/3)-προσεγγιστικός, PTAS. Διαφάνειες Προτεινόμενη μελέτη: Vazirani κεφ. 8 και κεφ. 10, DPV 9.2.4.
  • Διάλεξη 26/4/2023. Κυρτά σύνολα και κυρτή βελτιστοποίηση, η μέθοδος gradient descent. Online learning, learning from experts advice: αλγόριθμοι weighted majority και randomized weighted majority. 
  • Διάλεξη 3/5/2023. Εισαγωγή στο γραμμικό προγραμματισμό: γεωμετρία, κορυφές και βασικές εφικτές λύσεις, η μέθοδος simplex. 
  • Διάλεξη 11/5/2023. Δυϊκότητα στο γραμμικό προγραμματισμό. Εφαρμογή γραμμικού προγραμματισμού στο σχεδιασμό και την ανάλυση προσεγγιστικών αλγόριθμων. 
  • Διάλεξη 17/5/2023. Προσεγγιστικοί αλγόριθμοι βασισμένοι σε Γραμμικό Προγραμματισμό: Η βασική ιδέα / προσέγγιση του να χρησιμοποιήσουμε Γραμμικό Προγραμματισμό για να σχεδιάσουμε και να αναλύσουμε προσεγγιστικούς αλγόριθμους, ILP formulations και LP relaxations, randomized rounding για το πρόβλημα Set Cover, randomized (και deterministic) rounding για το πρόβλημα VLSI routing, συγκέντρωση γύρω από τη μέση τιμή, Chernoff-Hoeffding bounds (δείτε lecture notes), Max-Cut, Semidefinite Programming και o αλγόριθμος Goemans-Williamson για το πρόβλημα MAX-CUT (δείτε lecture notes).
  • Διάλεξη 24/5/2023. Πιθανοτικοί Αλγόριθμοι: η πιθανοτική μέθοδος και το Lovasz Local Lemma (δείτε lecture notes για το LLL και εφαρμογές του), αλγοριθμική εκδοχή LLL - η μέθοδος της εντροπίας (δείτε lecture notes και lecture notes). To secretary problem (δείτε ακόμη εδώ για secretary problems) και το prophet inequality. Σύντομη εισαγωγή στις βασικές έννοιες της Θεωρίας Παιγνίων (παίγνια σε κανονική μορφή, κυρίαρχες στρατηγικές, ισορροπία Nash στις αμιγείς και στις μεικτές στρατηγικές), ισορροπία Nash σε παίγνια 2 παικτών με μηδενικό άθροισμα, min-max θεώρημα von Neumann (δείτε lecture notes), fictitious play. 
  • Διάλεξη 31/5/2023. Εισαγωγή στον σχεδιασμό μηχανισμών. Δημοπρασίες για ένα αντικείμενο. Οι δημοπρασίες 1ης και 2ης τιμής. Σχεδιασμός μηχανισμών για single-parameter bidders, Λήμμα Myerson. Διαφάνειες. Σημειώσεις από το μάθημα του Tim Roughgarden: σχεδιασμός μηχανισμών και Myerson's Lemma. Multi-dimensional bidders, complements and substitutes, subadditive, submodular και superadditive valuation functions.  Διαφάνειες. Σημειώσεις από το μάθημα του Tim Roughgarden: εφαρμογές λήμματος Myerson στον σχεδιασμό μηχανισμών και VCG μηχανισμός. 

  
  
• 

  Γραπτές Ασκήσεις

  • Θα ανακοινωθούν δύο (2) σειρές γραπτών ασκήσεων. 
  • Οι γραπτές ασκήσεις υποβάλλονται στη σελίδα του μαθήματος, στο helios. Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
  • Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά, π.χ. αφού αφιερώσετε ικανό χρόνο ατομικής προσπάθειας), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τη λύση. Πανομοιότυπες διατυπώσεις θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές ασκήσεων.
    

  
  

  Εκφωνήσεις Γραπτών Ασκήσεων

  • 1η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 2/5/2023. 
  • 2η σειρά γραπτών ασκήσεων. Προθεσμία υποβολής: 30/6/2023. 

  
  

  • Υποβολή 1ης Σειράς Γραπτών Ασκήσεων Assignment
  • Υποβολή 2ης Σειράς Γραπτών Ασκήσεων Assignment
• 

  Προγραμματιστικές Ασκήσεις

  • Θα ανακοινωθεί μία (1) σειρά προγραμματιστικών ασκήσεων, με δύο σκέλη. 
  • Οι προγραμματιστικές ασκήσεις αφορούν την μοντελοποίηση απλών πρακτικών προβλημάτων βελτιστοποίησης σε (Ακέραιο) Γραμμικό Προγραμματισμό και στη χρήση της πλατφόρμας OR-tools της Google για την επίλυσή τους. 
  • Οι λύσεις των προγραμματιστικών ασκήσεων υποβάλλονται (σε μορφή notebooks και python scripts) στη σελίδα του μαθήματος, στο helios. Δεν γίνεται δεκτή η παράδοση ασκήσεων με e-mail.
  • Συνεργασία επιτρέπεται και μάλιστα ενθαρρύνεται (εάν γίνεται σωστά, π.χ. αφού αφιερώσετε ικανό χρόνο ατομικής προσπάθειας), αλλά τελικά κάθε φοιτητής πρέπει να διατυπώσει μόνος του τον κώδικά του. Πανομοιότυποι κώδικες θα εκλαμβάνονται ως αντιγραφή και δεν θα προσμετράται ο βαθμός τους, ενώ πιθανόν να υπάρξουν συνέπειες για όλες τις σειρές προγραμματιστικών και γραπτών ασκήσεων.

  
  

  • Εκφώνηση 1ης σειράς προγραμματιστικών ασκήσεων.
  • Προθεσμία υποβολής 1ου σκέλους: 30/5/2023
  • Προθεσμία υποβολής 2ου σκέλους: 30/6/2023

  • Παράδοση Προγραμματιστικών Ασκήσεων - 1ο σκέλος Assignment
  • Παράδοση Προγραμματιστικών Ασκήσεων - 2ο σκέλος Assignment
• 

  Material

  Not available