COMBINATORIAL OPTIMIZATION ALGORITHMS - APPROXIMATION ALGORITHMS

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, rounding the solution of linear programs, other methods based on properties of linear programming, and approximation schemes. learning outcomes

Semester Start Date: March 24, 2027

Day & Time: TBA by December

References:

1. V.V. Vazirani "Approximation algorithms", Springer-Verlag, 2001.
2. D.P. Williamson and D.B. Shmoys "The design of approximation algorithms," Cambridge University Press, 2011.

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.

There will be regular homework exercises that will be posted on the moodle website of the course. The plan is to have 6 homework assignments during the semester. The exercise is due to (approximately) two weeks after the last corresponding lecture (and the scanned solutions of the exercises will be submitted on the moodle website). Each student submits his/her own solutions to the homework assignments. In particular, while preparing the solutions it is forbidden to copy the solutions from someone else or to use an AI tool (such as ChatGPT, Gemini, Claude) to solve the assignments. After making the initial solution, it is recommended to ask one (or more) of the available AI tools for checking and grading the assignment prior to uploading it to the moodle website. It is allowed to modify the solutions based on the comments of the AI tools, but the student is supposed to be responsible for his/her submitted solutions and will be able to answer queries regarding the solutions in a later point in time.

At the end of the semester there will be an oral exam whose date will be coordinated between the lecturer and the students. The oral exam (apx. one hour taking place as a zoom meeting) will be on the homework assignments as well as the material studied during the course. The final grade will be the grade on the oral exam.

1. Deterministic Models in Operations Research (we will use the chapters on linear programming including duality, extreme points, totally unimodular matrices etc.).2. Data Structures and Algorithms – formally it is not required, but it is recommended.

There will be regular homework exercises that will be posted on the moodle website of the course.