Subject: Subject Sylbus: Combinatorial Optimization Algorithms - 096350

Combinatorial Optimization Algorithms - 096350
Credit
Points
2.0
 
Given In
Semester
a
 
  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, 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.




Textbooks
PublishedPublisherAuthorsBook
2011cambridge university pressd.p. williamson and d.b. shmoysthe design of approximation algorithms
2001springer-verlagv.v. vaziraniapproximation algorithms

Created in 08/03/2021 Time 14:56:44