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.

Problem Sets

Other course notes and resources