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, Local-Search, 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.