General Information
Course Website: http://www.cs.ubc.ca/~nickhar/W13
Lecture Time: Mondays &
Wednesdays, 9:30am11:00am
Lecture Room: ICICS 206
Instructor: Prof. Nicholas
Harvey, X851, nickhar@cs.ubc.ca
This
is a graduate course on algorithm design. We will explore two branches of this
field: combinatorial optimization algorithms and spectral algorithms. The
ultimate goal of the course is to explore the theme of “sparse approximations”
in graph theory. We will discuss thin trees, thin forests, expanders and graph sparsifiers.
Lectures

Date 
Topics 
Scribe 
References 
1 
1/2 
Review of
linear programming 
Nick
Harvey: PDF 
Goemans' notes pages 15 Combinatorial
Optimization Appendix A 
2 
1/7 
Strong
duality, FourierMotzkin Elimination, Farkas' Lemma 
Samira Samadi: PDF 
Goemans' notes pages 15 Understanding
and Using Linear Programming 6.4, 6.7 
3 
1/9 
Extreme
points 
Daniel
Busto: PDF 
Goemans' notes pages 510 Theory
of Linear and Integer Programming 8.3, 8.4, 8.5 
4 
1/14 
The
Ellipsoid Method 
Alex Frechette: PDF 
My Slides
PPTX, PDF, My extra
notes PDF Goemans' notes pages 16 Boyd’s
slides, Boyd’s
lecture, Boyd’s
lecture continuation Theory
of Linear and Integer Programming Ch 13, 14 
5 
1/16 
Integer
programs, Total unimodularity, Maxflow Mincut 
Samira Samadi: PDF 
Goemans' notes pages 1317 Goemans' notes pages 16 Combinatorial
Optimization 3.2, 6.5 
6 
1/21 
Min cost
cycle cover, Asymmetric TSP 
Zachary Drudi: PDF 
Chekuri's slides 2139 Frieze, Galbiati, Maffioli, Section
6 
7 
1/23 
Contraction
algorithm for minimum cut 
Nick
Harvey: PDF 
Combinatorial
Optimization pages 7678 
8 
1/28 
LP
relaxation of ATSP 
Daniel Busto:
PDF 

9 
1/30 
Randomized
rounding for ATSP 
Gabriel Goh: PDF 

10 
2/4 
The
spanning tree polytope 
Alex Frechette: PDF 
Combinatorial
Optimization p1517 
11 
2/6 
Pipage rounding 
Alex Frechette: PDF 

12 
2/13 
Thin
trees via pipage rounding 
Noushin Saeedi: PDF 

13 
2/25 
O(log n /
log log n) approximation for ATSP 
Zachary Drudi: PDF 

14 
2/27 
The Laplacian of a graph 
Gabriel Goh: PDF 

15 
3/4 
Thin
forests 
Gabriel Goh: PDF 

16 
3/6 
Thin
forests 
Zachary Drudi: PDF 
Using
ideas from the Batson et al paper 
17 
3/11 
Definition
of expanders 
Monir Hajiaghayi: PDF 

18 
3/13 
Algorithm
to construct expanders 
Daniel
Busto: PDF 
Using
ideas from the Batson et al paper 
19 
3/18 
Graph sparsifiers 
Samira Samadi: PDF 

20 
3/20 
Approximation
for Max Cut 
Alex Frechette: PDF 

21 
3/25 
Random
matrices 
Zachary Drudi: PDF 
Tropp's
paper, Tropp's survey, My notes on symmetric
matrices 
22 
3/27 
Tropp's inequality 
Zachary Drudi: PDF 

23 
4/3 
Random
graph sparsifiers 
Samira Samadi: PDF 
The
topics that we hoped to cover but couldn't fit in are:
·
Matroids, Matroid Polyhedra, Graph skeletons, Cut sparsifiers,
Negatively dependent distributions, Cheeger's
inequality