Advanced Heuristic and Approximation Algorithms

This course will focus on algorithms and heuristics for discrete optimization problems. We will study algorithmic techniques based on combinatorial and spectral methods as well as approaches based on rounding mathematical programming formulations of discrete optimization problems. We will also study efficient algorithms for solving such relaxations.

The main areas of application will be graph partitioning (e.g. minimum cut and maximum cut), graph traversal (e.g. Chinese postman problem and traveling salesman problem), randomized LP rounding (e.g. set cover and maximum satisfiability). We may also study graph decomposition (e.g. small set expansion).

(Tentative) Course Topics

Graph Partitioning:

Karger's Algorithm for Minimum Cut Goemans-Williamson Algorithm for Maximum Cut and Maximum-k-Cut Spectral Partitioning; Cheeger Inequality

Graph Traversal:

Traveling Salesman Problem Chinese Postman Problem Asymmetric Traveling Salesman Problem

Randomized LP Rounding:

Maximum Satisfiability Set Cover Dominating Set in Digraphs

Time Permitting:

Arora-Barak-Steurer Algorithm for Small-Set Expansion/Unique Games Arora-Rao-Vazirani Algorithm for Sparsest Cut

Coordinator

Alantha Newman