Weekly outline

• Γενικά
  

  Γενικά

  Διδάσκοντες
  

  • Δημήτρης Φωτάκης, Αναπλ. Καθηγητής ( fotakis@cs.ntua.gr )
  • Άρης Παγουρτζής, Καθηγητής (pagour@cs.ntua.gr)

  
  

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

  
  

  • Γιάννης Παπαϊωάννου, Υ.Δ.
  • Παναγιώτης Πατσιλινάκος, Υ.Δ. 

  
  

  Διαλέξεις
  

  • Κάθε Τετάρτη 16:00 – 19:00, μέσω Webex, στο link:  https://centralntua.webex.com/centralntua/j.php?MTID=md0926d1a7577acbda61311c481956ee2 
    
    Οι διαλέξεις θα ξεκινήσουν την Τετάρτη 24 Φεβρουαρίου, 2021. 

  
  

  Περιεχόμενα

  • Προσεγγιστικοί αλγόριθμοι, λόγος προσέγγισης, 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 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.
    
  • Ε. Ζάχος, Α. Παγουρτζής, Π. Γροντάς. Υπολογιστική Κρυπτογραφία. Κάλλιπος 2015.
  • M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh. Parameterized Algorithms. Springer, 2016.

  Σελίδες παλαιότερων ετών:  2019-20   2018-19   2017-18   2016-17      
  

  • Ανακοινώσεις Forum
• 22 February - 28 February
  

  22 February - 28 February

  Διάλεξη 24/2: Γραμμικός Προγραμματισμός, Simplex

  
  

  • Τοπική αναζήτηση για προβήματα κυρτής βελτιστοποίησης, γραμμικός προγραμματισμός, γεωμετρία, κορυφές και βασικές εφικτές λύσεις, η μέθοδος Simplex.