# 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

### 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.