This is an elective course, offered for both undergrad and grad students.
It introduces designing polynomial-time algorithms to compute approximate solutions for NP-hard optimization problems.
Specifically, the following topics are planned to be covered -
First, approximations with standard algorithm design techniques are presented: greedy, divide and conquer, local search, dynamic programming, random sampling, etc. Then, algorithms based on techniques native to approximations are explored: rounding with grid, deterministic rounding of LP, randomized rounding of LP, primal-dual method, region growing, shifting, tree metrics, coresets, epsilon-nets, etc.
The reductions to provide worst-case lower bounds on approximation factors achievable with polynomial-time algorithms are introduced.
Problems pursued include the following:
combinatorial set cover, geometric set cover, disk cover;
clustering, facility location;
cuts, TSP, Steiner tree, tree metrics, buy-at-bulk, matchings, shortest paths, spanner networks;
knapsack, bin packing, graph colouring, max SAT, scheduling.
Many exciting algorithmic ideas that repeatedly occur in algorithm design are emphasized throughout.