Course Identification
Approximation Algorithms (Introduction)
Lecturers and Teaching Assistants
Prof. Uriel Feige
Course Schedule and Location
Wednesday, 14:15 - 16:00, Jacob Ziskind Building, Rm 155
07/11/2018
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
Comments
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
27/02/2019
Estimated Weekly Independent Workload (in hours)
Syllabus
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).
Learning Outcomes
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.
Reading List
Course will make use of (but is not limited to) the book (available online) The Design of Approximation Algorithms, by Williamson and Shmoys.