ORIE 6334: Bridging Continuous and Discrete Optimization
Fall 2019
Instructor Information
Instructor: |
David P. Williamson |
Office: |
Rhodes 236 |
Office hours: |
Tuesdays 1:30-2:30, Fridays 11-12, and by appointment |
Office phone: |
255-4883 |
Email: |
davidpwilliamson at cornell.edu |
Overview
The course meets Mondays and Wednesdays in Hollister 320 Upson 206 from 11:40AM-12:55PM. It is also broadcast to Cornell Tech, Bloomberg 091.
This course will consider the interplay between continuous and discrete optimization broadly speaking, but with a focus on algorithmic spectral graph theory and applications of the multiplicative weights update paradigm. Within algorithmic spectral graph theory, both older structural results and recent algorithmic results will be presented. Topics to be covered include the matrix-tree theorem, Cheeger's inequality, Trevisan's max cut algorithm, bounds on random walks, Laplacian solvers, electrical flow and its applications to max flow, spectral sparsifiers, and the Colin de Verdiere invariant. Additional topics may include the Arora-Rao-Vazirani algorithm for sparsest cut, online algorithms for set cover and other problems, and results on maximizing submodular function maximization under various types of constraints.
Handouts
Handout 1: Course Information
Scribing materials
LaTeX macros for scribing
Lectures
Sept 4 |
Introduction. Something old: bounds on d-regular Moore graphs of diameter two. (Hoffman-Singleton 1960) |
Sept 9 |
Something old, something new: Eigenvalue interlacing. Wilf's theorem. Huang's proof of the sensitivity conjecture. (Huang 2019) |
Sept 11 |
The multiplicative weight update algorithm. Application to packing LPs. (Arora, Hazan, Kale 2012) |
Sept 16 |
Application of multiplicative weight algorithm to max flow and max multicommodity flow. |
Sept 18 |
Eigenvalue basics. |
Sept 23 |
More eigenvalue basics. The spectra of bipartite graphs. |
Sept 25 |
Laplacians, and some bounds on graph properties. |
Sept 30 |
The Matrix-Tree theorem. |
Oct 2 |
Normalized Laplacians. Types of cuts. The Cheeger inequality. |
Oct 7 |
Continued proof of the Cheeger inequality. Trevisan's inequality. |
Oct 9 |
Continued proof of Trevisan's inequality and an application to MAX CUT. |
Oct 14 |
No class: Fall break. |
Oct 16 |
Generalized Laplacians, the Colin de Verdiere parameter, and graph planarity. |
Oct 21 |
No class: INFORMS. |
Oct 23 |
No class: INFORMS. |
Oct 28 |
Introduction to electrical flow. |
Oct 30 |
Low-stretch spanning trees. |
Nov 4 |
Iterative methods and preconditioners. |
Nov 6 |
A simple combinatorial algorithm for electrical flow. |
Nov 11 |
Max flow in undirected graphs. |
Nov 13 |
Spectral sparsifiers. |
Nov 18 |
Matrix multiplicative weights and deterministic sparsifiers. |
Nov 20 |
Linear-sized sparsifiers. |
Nov 25 |
Multiplicative weights and online set cover. (Buchbinder and Naor, 2007) |
Nov 27 |
No class: Thanksgiving break. |
Dec 2 |
No class: Snow day. |
Dec 4 |
Discrepancy minimization and multiplicative weights. (Levy, Ramadas, Rothvoss, 2017). |
Dec 9 |
Submodular function maximization. (Buchbinder and Feldman, 2017) |
Problem Sets
Other course notes and resources
- My Fall 2016 course on algorithmic spectral graph theory.
- Lap Chi Lau, University of Waterloo
- Dan Spielman, Yale University
- Luca Trevisan, UC Berkeley and Bocconi University
- Chris Godsil and Gordon Royle, Algebraic Graph Theory.