Approximation & Online Algorithms (Fall ’24)

Description: Many optimization problems are NP-hard, which means that one cannot expect an algorithm to be computationally efficient and make optimal decisions. These “hard” optimization problems arise in various applications such as network design, scheduling, transportation, supply-chain and robotics. Approximation algorithms provide a theoretically sound approach to such problems by obtaining provably near-optimal solutions efficiently. Furthermore, many applications involve uncertain or dynamic data, where an algorithm has to make decisions without complete information. In order to handle such situations, we will extend the notion of approximation algorithms to “online” algorithms for stochastic inputs (when probabilistic information is available) as well as adversarial inputs (when no future information is available). The course will focus on fundamental and broadly applicable techniques such as greedy algorithms, local search, dynamic programming, linear/convex programming, primal-dual algorithms, potential-function methods and decision-tree methods. These techniques will be demonstrated in the context of basic optimization problems such as facility location, matching, scheduling and set cover. All topics involve mathematical proofs.