Προσεγγιστικοί Αλγόριθμοι και Σχεδιασμός Μηχανισμών
εαρινό εξάμηνο 2012-2013
Γενικά
Διδάσκοντες
- Στάθης Ζάχος, Καθηγητής ()
- Δημήτρης Φωτάκης, Λέκτορας ()
Βοηθοί Διδασκαλίας
- Μάρκος Επιτρόπου, Υ.Δ. ()
- Θοδωρής Λυκούρης, Υ.Δ. ()
Διαλέξεις
- κάθε Πέμπτη 16:00-20:00 (1.1.31, παλιό κτήριο Ηλεκτρολόγων)
Ώρες Γραφείου
- κάθε Δευτέρα 15:00-16:00 στο εργαστήριο 1.1.3 (CoReLab) ή στο γρ. 1.1.10 του κτηρίου Ηλεκτρολόγων.
- κάθε Πέμπτη 15:00-16:00 στο εργαστήριο 1.1.3 (CoReLab) ή στο γρ. 1.1.10 του κτηρίου Ηλεκτρολόγων.
Ανακοινώσεις
Υλικό
Διαφάνειες Μαθήματος
- Διάλεξη 7/3/2013: Εισαγωγή και Διαδικαστικά. Προσεγγιστικοί Αλγόριθμοι για NP-∆ύσκολα Προβλήματα ([4]: 1, 3.2 [5]: 1.1-1.6, 2.3-2.4).
- Διάλεξη 14/3/2013: Μη προσεγγισιμότητα. Προσεγγιστικοί αλγόριθμοι βασισμένοι σε γραμμικό προγραμματισμό: deterministic και randomized rounding ([4]: 14, [5]: 1.3, 1.7).
- Διάλεξη 21/3/2013: Randomized rounding: Set Cover, Max Sat, Max Cut ([4]: 16, 26.1-26.4, [5]: 5.1-5.6, 6.1-6.2).
- Διάλεξη 4/4/2013: LP Duality. Dual Fitting Analysis, The Primal Dual Method: Set Cover ([4]: 13.1, 15, [5]: 7.1). Facility Location ([5]: 4.5).
- Διάλεξη 18/4/2013: Polynomial Time Approximation Schemes. Graph Partitioning Problems.
- Διάλεξη 25/4/2013: Hardness of Approximation. ([5]: 16)
- Διάλεξη 16/5/2013: Introduction to Mechanism Design. ([8]: 9)
- Διάλεξη 23/5/2013: Computationally Efficient Truthful Mechanisms. ([8]: 11, 12)
- Διάλεξη 30/5/2013: Imposibility Results. Characterisations. Verification.
- Διάλεξη 6/6/2013: Social Choice.
- Διάλεξη 13/6/2013: Approximate Mechanism Design without Money.
- Διάλεξη 20/6/2013: Diffusion in Networks.
Συμπληρωματικό Υλικό
- M.X. Goemans. An Introduction to Linear Programming. Lecture Notes, MIT, 1994.
- M.X. Goemans. Advanced Algorithms, MIT, Fall 2001.
- A. Procaccia. Social Choice I. Social Choice II. Lecture Notes, CMU, Spring 2012.
- V. Conitzer. Voting and Social Choice. Lecture Notes, Duke University, Fall 2011.
- T. Zinchenko. Voting Manipulation. Lecture Notes, MPI, Fall 2013.
- J. Hartline. Lectures on Optimal Mechanism Design. Lecture Notes, Northwestern University, 2005.
- E. Koutsoupias. Scheduling without payments. 2011.
- D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. 2003.
Βιβλιογραφία
- H. Karloff. Linear Programming. Birkhäuser, 1991.
- V. Chvatal. Linear Programming. W. H. Freeman, 1983.
- C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover, 1998.
- V. V. Vazirani. Approximation Algorithms. Springer, 2001.
- D. B. Shmoys and D. P. Williamson. The Design of Approximation Algorithms. Cambridge University Press, 2011 (Μπορείτε να το βρείτε εδώ).
- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
- M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005.
- N. Nisan, T. Roughgarden, E. Tardos and V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007 (Μπορείτε να το βρείτε εδώ).
- Y. Shoham and K. Leyton-Brown. Multiagent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press, 2009 (Μπορείτε να το βρείτε εδώ).
- D. Easley and J. Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, 2010 (Μπορείτε να βρείτε μια draft έκδοση εδώ).
Ασκήσεις
Γραπτές Ασκήσεις
| Εκφώνηση | Ημερομηνία Παράδοσης | Σχέδιο Λύσεων |
|---|---|---|
| [4]: 18.1, 18.2. [5]: 1.5, 2.5, 2.6, 4.7, 5.6, 6.6 | 23/5/2013 |
|
| Δεύτερη Σειρά |