Combinatorial Optimization Algorithms  096350





Lecture 
Exercise 
Laboratory 
Project or Seminar 
House Work 
Weekly Hours 
2 



6 

Determination of the grade according to progress during the semester.
Prerequisites:
    Deterministic Models in Oper.Research 
094313
 
The Course Focuses on the Design of Fast Algorithms for Solving Combinatorial Optimization Problems, and Analyzing the Ratio Between the Value of the Returned Solution and the Optimal One. the Studied Algorithmic Methods Are: Combinatorial Methods, Greedy Algorithms, LocalSearch, Rounding the Solution of Linear Programs, and Approximation Schemes. at the End of the Course the Student Will Be Able to:
1. Explain the Notions and Definitions in Theoretical Analysis of Approximation Ratio.
2. Discuss the Advantages and Disadvantages of Theoretical Analysis of Algorithms.
3. Design An Algorithm for a New Variant of a Combinatorial Optimization Problem That Is Similar to the Problems Studied in Class.
4. Find Bad Examples for Algorithms for Combinatorial Optimization Problems.
5. Prove Bounds on the Optimal Value and Use These to Analyze An Approximation Algorithm.
6. Choose Among Different Methods for Approximating Combinatorial Optimization Problems.
TextbooksPublished  Publisher  Authors  Book 

2011  cambridge university press  d.p. williamson and d.b. shmoys  the design of approximation algorithms 
2001  springerverlag  v.v. vazirani  approximation algorithms 
Created in 08/03/2021 Time 14:56:44