Mini-Course on LP and SDP Rounding (IRIF, Paris, Spring 2020)

Instructor

Prerequisites

Basic familiarity with graph algorithms.

Objectives

Math programming methods used in approximation algorithms have found successful applications to various problems in graph theory. In this mini-course, we will present some classical approaches for rounding linear and semi-definite programs. We will show applications of these techniques to combinatorial problems such as kernels and dominating sets in digraphs, triangle transversals, max-k-cut and graph coloring.

Course Outline

LP Randomized Rounding (basic concepts such as extreme points, duality, complementary slackness)

Applications: Dominating sets in digraphs, kernels, semi-kernels, arc colored digraphs, asymmetric k-center, triangle transversals

SDP Rounding (basic concepts such as problem formulations, normal distribution, random hyperplane rounding)

Applications: Max-k-cut, graph coloring, theta function and perfect graphs, unique games (time permitting)

Lecture Schedule

Lecture I	February 13	LP rounding: Triangle transversals (using complementary slackness), Bin packing (using extreme point structure)
Lecture II	February 14	LP rounding: Randomized set-cover rounding, Applications to directed graph theory
Lecture III	February 18	SDP rounding: Max-Cut, Coloring 3-colorable graphs
Lecture IV	February 20	SDP rounding: Finding large stable sets, Max-k-cut

Useful Resources

The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys
Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan at UC Berkeley
Iterative Methods in Combinatorial Optimization by Lap Chi Lau, R. Ravi and Mohit Singh
Cornell University Course on Mathematical Programming by David P. Williamson