Basic Information
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. Learning Outcomes# 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.
Faculty: Data and Decision Sciences
|Undergraduate Studies
|Graduate Studies
Pre-required courses
94312 - Deterministic Mod.in Operations Research or 94313 - Deterministic Models in Oper.research