Approximation Algorithms (Introduction)
Lecturers and Teaching Assistants
Prof. Uriel Feige
Course Schedule and Location
Wednesday, 14:15 - 16:00, Ziskind, Rm 155
Field of Study, Course Type and Credit Points
Mathematics and Computer Science: Lecture; Elective; 2.00 points
Mathematics and Computer Science (Systems Biology / Bioinformatics): Lecture; Elective; 2.00 points
In addition, if there will be sufficient interest, a more advanced course will be given in the second semester.
Course location- room 155 at Ziskind. on 2/1/2019 the lecture will be held at FGS room
Attendance and participation
Scheduled date 1
Estimated Weekly Independent Workload (in hours)
Many combinatorial optimization problems are NP-hard. For such problems, approximation algorithms provide near optimal solutions in polynomial time. We shall present algorithmic techniques that are commonly used (such as greedy algorithms, dynamic programming, linear and semidefinite programming relaxations, various rounding procedures), show how they are analysed, and discuss also limitations of approximation algorithms (hardness of approximation).
Upon successful completion of this course students should be able to:
Develop an understanding and become familiar with standard algorithmic techniques that suffice for the design and analysis of basic approximation algorithms, and for understanding scientific papers in this area.
Course will make use of (but is not limited to) the book (available online) The Design of Approximation Algorithms, by Williamson and Shmoys.