Optimization and Approximation (ENS Lyon, M1 2016-2017)

Course Staff

Instructor:

TAs:

Objective

The goal of this course is to study techniques for solving discrete optimization problems with a focus on linear/convex relaxations and their applications to approximation algorithms.

Course Topics

Background on polytopes

Simplex algorithm

Duality and complementary slackness

Integer polytopes (matchings, flows, spanning trees)

Integer solutions (Branch-and-bound)

Basic rounding techniques (deterministic, randomized)

Iterative rounding

Dual fitting

Primal-dual algorithms

Algorithms for convex programs (Ellipsoid)

Exponential-sized LPs: separation oracles and cutting planes

Semidefinite programming (Max-Cut and Max-2-SAT)

Lecture Schedule

Introduction	Wednesday	September 14	Lecture 1
Geometry of Linear Programming	Tuesday	September 20	Lecture 2
Simplex Algorithm	Tuesday	September 27	Lecture 3
Pivot Rules and Degeneracy	Friday	September 30	Lecture 4 Homework 1
Duality	Tuesday	October 4	Lecture 5
Integer Solutions	Tuesday	October 18	Lecture 6
MIDTERM EXAM	Tuesday	October 25	Midterm Solutions
Efficient Convex Optimization	Tuesday	November 8	Lecture 7
LP Rounding	Tuesday	November 15	Lecture 8
Primal-Dual/Dual Fitting	Tuesday	November 22	Lecture 9 Homework 2 Solutions
SDP and Graph Partitioning	Tuesday	December 6	Lecture 10
Coloring via SDP	Tuesday	December 13	Lecture 11
Deterministic Rounding	Tuesday	January 3	Lecture 12
Rounding via Rank Lemma	Tuesday	January 10	Lecture 13
Convex Combinations + TSP Algorithms	Tuesday	January 31	Lecture 14
FINAL EXAM	Tuesday 9h-12h	February 7	Final Exam I Solutions Final Exam II

TD Schedule

Problem Modeling and Formulations	Friday	September 23	TD 1
Geometry/Simplex Algorithm	Friday	October 7	TD 2
Simplex Algorithm	Tuesday Amphi B, 10h15-12h15	October 11	TD 3
Duality	Friday	October 14	TD 4
Midterm Review	Friday	October 21
Integer Solutions	Friday	November 4	TD 6
Separation Oracles and LP Rounding	Friday	November 18	TD 7
Primal-Dual Algorithms	Friday	November 25	TD 8
Semidefinite Programming	Friday	December 9	TD 9
Graph Coloring	Friday	December 16	TD 10
Extreme Point Structure	Friday	January 6	TD 11
Iterative Rounding	Friday	January 13	TD 12
Convex Combinations + Review	Friday	February 3	TD 13

Useful Resources

Linear Programming: Foundations and Extensions by Robert J. Vanderbei
Approximation Algorithms by Vijay V. Vazirani
The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys
Iterative Methods in Combinatorial Optimization by Lap Chi Lau, R. Ravi and Mohit Singh
Cornell University Course on Mathematical Programming by David P. Williamson