| Τομέας |
Θεμελιώσεις της Επιστήμης των Υπολογιστών και Εφαρμογές |
| Διδάσκων | Καθηγητής Παύλος Σπυράκης |
| Ώρες Διδασκαλίας | Δευτέρα 17:00 - 19:00, Αίθουσα Σεμιναρίων (1ος όροφος κτιρίου Β) |
28/02/12 Οι παραδόσεις του μαθήματος για το ακαδημαϊκό έτος 2011-2012 θα αρχίσουν τη Δευτέρα, 5 Μαρτίου 2012.
Η διδακτέα ύλη βασίζεται στο βιβλίο "Approximation Algorithms" του Καθηγητή Vijay V. Vazirani,
το οποίο υπάρχει στη βιβλιοθήκη του τμήματος. Τα σημαντικότερα κεφάλαια του βιβλίου μπορείτε
να τα βρείτε εδώ.
Μέρος Ι: Συνδυαστικοί Αλγόριθμοι
Εισαγωγή (κεφάλαιο 1)
Set-cover (κεφάλαιο 2)
Metric-TSP (κεφάλαιο 3)
Multiway Cut and k-Cut (κεφάλαιο 4)
Knapsack (κεφάλαιο 8)
Bin Packing (κεφάλαιο 9)
Minimum makespan scheduling (κεφάλαιο 10)
Μέρος ΙΙ: Αλγόριθμοι βασιζόμενοι σε γραμμικό προγραμματισμό
LP-duality (κεφάλαιο 12)
Dual Fitting (κεφάλαιο 13)
Τεχνική Στρογγυλοποίησης (Rounding) (κεφάλαιο 14)
Primal-dual schema (κεφάλαιο 15)
MAX-SAT Derandomization (κεφάλαιο 16)
Scheduling unrelated parallel machines (κεφάλαιο 17)
Semidefinite Programming (κεφάλαιο 26)
Επίσης, στην ύλη περιλαμβάνεται και το paper "Playing Large Games using Simple Strategies (2003)", Richard J. Lipton, Evangelos Markakis, Aranyak Mehta.
Αpproximation Algorithms: Vijay V. Vazirani. Springer Verlag, ISBN: 3540653678, 2001.
Complexity and Approximation Combinatorial optimization problems and their approximability properties:
G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi.
Springer Verlag, ISBN 3-540-65431-3, 1999.
Approximation Algorithms for NP-Hard Problems: Dorit S. Hochbaum (editor), Brooks/Cole.
Collection of Lecture Notes, Surveys, and Papers
Approximation algorithms Project, Research, Theory group at Nada, KTH
Links to combinatorial sites by Oxford Combinatorics Group.
CS 460b/560b - Theoretical Methods in Computer Science Course, Laszlo Lovasz.