ΘΕΩΡΙΑ  ΑΠΟΤΕΛΕΣΜΑΤΙΚΩΝ  ΠΡΟΣΕΓΓΙΣΤΙΚΩΝ  ΑΛΓΟΡΙΘΜΩΝ

 

[Ανακοινώσεις] [Ύλη] [Βιβλιογραφία] [Σύνδεσμοι]

 


Τομέας

Θεμελιώσεις της Επιστήμης των Υπολογιστών και Εφαρμογές

Διδάσκων

Καθηγητής Παύλος Σπυράκης

Ώρες Διδασκαλίας

Δευτέρα 17:00 - 19:00, Αίθουσα Σεμιναρίων (1ος όροφος κτιρίου Β)

 


Ανακοινώσεις

28/06/13     Η εξέταση του μαθήματος θα είναι γραπτή και θα πραγματοποιηθεί την Παρασκευή 5 Ιουλίου 2013 και ώρα 17:00-20:00 στην αίθουσα Β4.
27/02/13     Οι παραδόσεις του μαθήματος για το ακαδημαϊκό έτος 2012-2013 θα αρχίσουν τη Δευτέρα, 4 Μαρτίου 2013. Το μάθημα θα διδάσκεται κάθε Δευτέρα, 5:00-7:00μμ, στην αίθουσα ΑΣ1 (κτίριο Β, 1ος όροφος, πριν τη γραμματεία του προέδρου).


 

Ύλη

Η διδακτέα ύλη βασίζεται στο βιβλίο "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.
Electronic Colloquium on Computational Complexity Research reports, surveys and books in computational complexity
CS 460b/560b - Theoretical Methods in Computer Science Course, Laszlo Lovasz.
Algorithmic courses on WWW by Kirk Pruhs.
ChE 469: Approximation Algorithms, Instructor: Nick Sahinidis (nikos@uiuc.edu), University of Illinois at Urbana-Champaign.