Approximation & Online Algorithms

Instructor: Viswanath Nagarajan (IOE 2713)

Term: Winter 2021

Lectures: Mondays and Wednesdays, 10:30 — 12:00PM, virtual. 

Description: Many optimization problems are NP-hard, which means that one cannot expect an algorithm to be computationally efficient and make optimal decisions. Furthermore, many applications involve dynamic or online data, where an algorithm has to make decisions even without complete information. These “hard” optimization problems arise in various applications such as network design, scheduling, transportation, supply-chain and robotics. The common approach to such problems is via approximation and online algorithms. Approximation algorithms bypass the computational difficulty by obtaining near-optimal solutions efficiently. Online algorithms obtain near-optimal solutions even when future input is unknown. This course will cover basic techniques in the design and analysis of approximation and online algorithms, which includes greedy algorithms, local search, dynamic programming, linear/convex programming, primal-dual algorithms and potential-function methods. These techniques will be demonstrated in the context of basic combinatorial optimization problems such as facility location, matching, scheduling, set cover, Steiner network and multicommodity routing. All the topics will involve mathematical proofs. 

Course outline and lecture notes

Greedy: min spanning tree, max-coverage, set cover. Notes 1.

Local search: max matching, k-median. Notes 2.

Dynamic programming: independent set on trees, longest path on DAGs, knapsack, Euclidean TSP. Notes 3.

Linear programming: min cut, set cover, non-metric and metric facility location, multicommodity routing, k-sparse set cover, Steiner forest, generalized assignment. Notes 4.

Online basics: rent-or-buy (ski rental), line search (online bidding), deterministic and randomized lower bounds. Notes 5.

Online primal-dual: fractional covering/packing LPs, set cover, throughput maximization. Notes 6.

Online dual fitting: bipartite matching, Steiner tree and forest, randomized matching. Notes 7.

Online potential functions: flowtime scheduling, load balancing, set cover, experts. Notes 8.