Weekly outline

  • Γενικά

    Διδάσκοντες


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


    Βοηθοί Ασκήσεων

    • Ευαγγελία Γεργατσούλη
    • Αλέξανδρος Τσιγώνιας


    Διαλέξεις

    • Τετάρτη 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.


    Σελίδα μαθήματος 2016-17


  • 19 February - 25 February

    21/2

    • 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.

      • 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.

        • 12 March - 18 March

          14/3

          • 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).

            • 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.

              • 2 April - 15 April

                Διακοπές Πάσχα

                • 16 April - 22 April

                  18/4


                  • 23 April - 29 April

                    25/4


                    • 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)


                      • 7 May - 13 May

                        9/5

                        Θεωρία αριθμών. Θεωρία ομάδων. Πιθανοτικοί έλεγχοι πρώτων αριθμών: Fermat test και Miller-Rabin test. Η χρήση του Θ. Lagrange στους πιθανοτικούς αλγορίθμους.

                        Διαφάνειες set 1: 1-54

                        Διαφάνειες set 2: 1-8 

                        (προσωρινές, θα γίνουν αλλαγές)

                        • 14 May - 20 May

                          18/5

                          Κατανεμημένοι αλγόριθμοι:


                          [Παρουσίαση: Ι. Παπαϊωάννου - Α. Παγουρτζής]


                          Προτεινόμενη μελέτη: μάθημα Principles of Distributed Computing, R. Wattenhofer (ETH Zurich): κεφ. 0, 1, 2, 3.



                          • 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

                              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

                                6/6

                                Παρουσιάσεις εργασιών φοιτητών. Πρόγραμμα παρουσιάσεων.