General Information
Course Website: http://www.cs.ubc.ca/~nickhar/W13
Lecture Time: Mondays &
Wednesdays, 9:30am-11: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 1-5 Combinatorial
Optimization Appendix A |
|
2 |
1/7 |
Strong
duality, Fourier-Motzkin Elimination, Farkas' Lemma |
Samira Samadi: PDF |
Goemans' notes pages 1-5 Understanding
and Using Linear Programming 6.4, 6.7 |
|
3 |
1/9 |
Extreme
points |
Daniel
Busto: PDF |
Goemans' notes pages 5-10 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 1-6 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, Max-flow Min-cut |
Samira Samadi: PDF |
Goemans' notes pages 13-17 Goemans' notes pages 1-6 Combinatorial
Optimization 3.2, 6.5 |
|
6 |
1/21 |
Min cost
cycle cover, Asymmetric TSP |
Zachary Drudi: PDF |
Chekuri's slides 21-39 Frieze, Galbiati, Maffioli, Section
6 |
|
7 |
1/23 |
Contraction
algorithm for minimum cut |
Nick
Harvey: PDF |
Combinatorial
Optimization pages 76-78 |
|
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 p15-17 |
|
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