-- as the course progress, topics covered in lectures are listed here ---
This is an elective course, offered to both undergrad and grad students.
It introduces designing polynomial-time algorithms to compute approximate solutions for optimization problems.
I have offered this course last time during Spring '19.
First, approximations using standard algorithm design techniques are presented, including greedy, divide-and-conquer, local search, dynamic programming, pruning, and random sampling.
Then, algorithms based on techniques native to approximations are explored, which include rounding the data, rounding linear programs, primal-dual method, region growing, grid shifting, tree metrics, coresets, and epsilon-nets.
Furthermore, reductions are introduced to provide worst-case lower bounds on the approximation factors that can be achieved with polynomial-time algorithms.
Problems pursued include the following:
set cover, knapsack, bin packing, scheduling, assignment, satisfiability;
spanning networks, Steiner networks, spanner networks, traveling salesman, subgraph search, cuts in graphs, congestion minimization, colouring;
disk cover, transversals, clustering, facility location.
This course is an extension of CS207; many exciting fundamental ideas that repeatedly occur in algorithm design are emphasized throughout, thereby providing insights into the rich structures underlying various algorithmic problems.