Advanced Heuristic and Approximation Algorithms (Grenoble INP, M2 2017-2018)

ORCO

Instructor

Alantha Newman

Objectives

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

Lecture Schedule

Useful Resources

1. The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys
   
2. Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan at UC Berkeley