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