Yildirim.bilkent.edu.tr

IE 519-01: Approximation Algorithms – Fall 2010 • Instructor: E. Alper Yıldırım, EA 311, Ext. 3442 (290 34 42 from outside of Bilkent), [email protected] • Time & Place: Tuesday, 13:40–15:30 and Thursday, 15:40–16:30, EA 322.
• Office hours: EAY: By appointment.
• Prerequisites: There are no formal prerequisites for this course. However, students will be expected to have some basic background in linear programming (at the level of IE 202) and integer programming (at the level of IE303).
• Recommended Textbook: We will not have a formal textbook in this course. However, the following textbooks are on reserve at the Bilkent library and will be useful: – Approximation Algorithms, Vijay V. Vazirani. Springer, 2003. Call number: QA76.9.A43 V39 2003 (on – Approximation Algorithm for NP-Hard Problems, edited by Dorit S. Hochbaum. PWS Publishing Company, 1997. Call number: T57.7 .A68 1997 (on reserve) Lecture Notes on Approximation Algorithms, by David P. Williamson. See – http://www.bilkent.edu.tr/~yildirim/handouts/williamson ibm.pdf – http://www.bilkent.edu.tr/~yildirim/handouts/williamson cornell.pdf • Course Description: This is an introductory level graduate course on approximation algorithms. The course covers combinatorial and mathematical programming techniques to derive approximation algorithms for NP-hardoptimization problems. Topics include greedy algorithms, approximation schemes via dynamic programming,rounding LP relaxations of integer programs, and semidefinite relaxations. The material will be complemented bythe implementation of selected algorithms in a high-level language such as MATLAB.
• Course Objectives: This course is aimed at familiarizing graduate students with the design, analysis, and implementation of algorithms for optimization problems.
• Homeworks: Homework will be assigned biweekly (approximately), and will be due in class on the due date.
• Homework Policy: No late homework will be accepted unless prior arrangements are made with the instructor. You are allowed to discuss questions with other students and with the instructor, however, everystudent is supposed to write up her/his own solutions. Since this is a graduate level class, a lot of emphasis willbe placed on your reasoning. Please be sure to explain your reasoning well. Please write legibly and remember tostaple. Some homework assignments will include the implementation of algorithms in MATLAB.
• Exams: There will be an in-class midterm (tentatively on Monday, November 10) and an in-class comprehensive final exam some time during the final exam period. The exact dates and places will be announced during thesemester.
• Make-up Policy: A make-up examination will only be given under highly unusual circumstances (such as serious The student should contact the instructor as early as possible and provide the instructor with proper documentation (such as a medical note certified by Bilkent University’s Health Center).
The (comprehensive) make-up exam will be given during or right after the final exam period.
• Grades: Your overall score will be computed based on 15% homework, 40% midterm, and 45% final exam.
• Important Note: Please make sure that you have a STARS password and a valid e-mail in the STARS system.
All of our communications including homework announcements and distribution of solution sets will be conductedthrough the STARS system.
– A Brief Introduction to the Complexity Theory – Algorithms based on Linear Programming and Duality – Algorithms based on Semidefinite Programming

Source: http://yildirim.bilkent.edu.tr/ie519syl.pdf