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

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. sparsest cut), graph traversal (e.g. asymmetric traveling salesman problem), randomized LP rounding (e.g. set cover and dominating set). We may also study graph decomposition (e.g. small set expansion). Note that this course will not be exactly the same as last year!

Course Topics

LP Rounding using Duality:
Triangle Transversals
Feedback Arc Set in Tournaments

Randomized LP Rounding:
Set Cover
Dominating Set in Digraphs

Expansion and Graph Partitioning:
Spectral Partitioning; Cheeger Inequality
Small-Set Expansion
Unique Games

Graph Traversal:
Hoffman Circulation Theorem
Asymmetric Traveling Salesman Problem

Algorithms for Data Analysis:
Johnson-Lindenstrauss Lemma
Hashing
Nearest Neighbor Search

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
3. Iterative Methods in Combinatorial Optimization by Lap Chi Lau, R. Ravi and Mohit Singh
4. Cornell University Course on Mathematical Programming by David P. Williamson
5. Stanford University Course on Algorithmic Techniques for Big Data by Moses Charikar