Θεωρητική Πληροφορική ΙΙ: Προσεγγιστικοί Αλγόριθμοι (ΣΗΜΜΥ, ΣΕΜΦΕ, ΜΠΛΑ)
εαρινό εξάμηνο 2008-2009
Γενικά
Διδάσκοντες
- Στάθης Ζάχος, Καθηγητής ()
- Άρης Παγουρτζής, Λέκτορας ()
- Δημήτρης Φωτάκης, Λέκτορας ()
Έναρξη μαθήματος
19/3/2009.
Διαλέξεις
- Πέμπτη 16:00-20:00, αίθουσα 1.1.29 (παλαιό) Κτήριο Ηλεκτρολόγων (ΕΜΠ)
Προαπαιτούμενα
Μαθήματα σε Αλγόριθμους και Πολυπλοκότητα.
Βιβλιογραφία
- Vijay Vazirani, Approximation Algorithms, 2003, Springer. (http://www.springer.com/computer/foundations/book/978-3-540-65367-7.)
Πληροφορίες
- Ε. Ζάχος, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 1.1.15. Τηλ. 210 7721646 - 44, fax: 210 7721645, email: .
- Α. Παγουρτζής, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 1.1.30. Τηλ. 210 7721644, fax: 210 7721645, email: .
- Δ. Φωτάκης, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, ΕΜΠ, Γραφείο 1.1.10. Τηλ. 210 7724302, fax: 210 7722509, email: .
Ανακοινώσεις
- Το μάθημα της Πέμπτης 2 Απριλίου 2009 δε θα πραγματοποιηθεί.
Υλικό
Παρουσιάσεις
| 19/3 | Δ. Φωτάκης | §§ 1, 2, 3.2 Αλγόριθμοι Προσέγγισης για NP-δύσκολα προβλήματα | Διαφάνειες |
| 26/3 | Γ. Καούρη | §§ 3.1 Steiner Tree | Διαφάνειες |
| §§ 4 Multiway Cut and k-Cut | Διαφάνειες | ||
| Ε. Μπαμπάς | §§ 6 Feedback Vertex Cover. | ||
| 9/4 | Α. Γκόμπελ | §§ 8 Knapsack | Διαφάνειες |
| §§ 9 Bin-Packing | |||
| Π. Ποτίκας | §§ 5 k-Center | Διαφάνειες | |
| §§ 10 Minimum Makespan Scheduling | Διαφάνειες | ||
| 30/4 | Α. Γαλάνης | The Probabilistic Method | Διαφάνειες |
| §§ 11 Euclidean TSP | Διαφάνειες | ||
| 7/5 | Μ. Πετούση | §§ 12 Introduction to Lp-Duality | Διαφάνειες |
| Ε. Μπακάλη | §§ 14 Rounding Applied to Set Cover | ||
| 14/5 | Π. Κουτρής | §§ 16 Maximum Satisfiability | |
| §§ 17 Scheduling on Unrelated Parallel Machines | |||
| 21/5 | Μ. Θάνος | §§ 22 Steiner Forest | Διαφάνειες |
| 28/5 | §§ 20 Multicut in General Graphs | Διαφάνειες | |
| Γ. Αγγελής | §§ 18 Multicut and Integer Multicomodity Flow in Trees | Διαφάνειες | |
| 4/6 | Δ. Φωτάκης | Congestion Games and Competitive Resource Allocation | Διαφάνειες | `
| 'Α. Παγουρτζής | Path Coloring | Διαφάνειες | |
| 11/6 | Β. Μαρκάκης | Tutorial: Approximate Nash Equilibria | Διαφάνειες |
| 18/6 | Β. Φυσικόπουλος | §§ 24 Facility Location | Διαφάνειες |
| Θ. Λιανέας | §§ 29 Hardness of Approximation | Διαφάνειες | |
| 25/6 | Ζ. Πιττουράς | §§ 26 Semidefinite programming | Διαφάνειες |
| Μ. Θάνος | §§ 23 Steiner Network |