MCS 521 - Combinatorial Optimization
University of Illinois - Chicago
Fall 2013

MCS 521 somewhat differs in topics each time it is offered. This year it will survey canonical problems and techniques in combinatorial optimization. Example topics include: linear and convex programming, spanning trees, matchings, flows, TSP, matroids, and approximation algorithms.

This course is represented in the combinatorics prelim.

Basic Information

Syllabus: pdf
Time and Location: TR 9:30am - 10:45am, Lincoln Hall (LH) 104
Instructor Contact Information: Lev Reyzin, SEO 713, (312)-413-9576,
Textbook: W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver.  Combinatorial Optimization
Office Hours: W 11:00am - 12:00pm, R 10:45am - 11:45am

Exam

The in-class final exam will be held on Thursday December 5, 2013 9:30-10:45am.

Presentations

instructions
topics and times

Problem Sets

problem set 1 due 9/24/13
problem set 2 due 10/15/13
problem set 3 due 11/26/13

Lectures and Readings

Note: lectures will have material not covered in the readings.

Lecture 1 (8/27/13)
covered material: intro to the course, intro to Linear Programming
textbook chapter: appendix A

Lecture 2 (8/29/13)
covered material: Fourier-Motzkin Elimination, Farkas' Lemma and its geometric interpretation
textbook chapter: appendix A, continued

Lecture 3 (9/3/13)
covered material: weak and strong duality for LPs, Complementary Slackness
textbook chapter: appendix A, continued

Lecture 4 (9/5/13)
covered material: how FME can solve LPs, the Simplex algorithm, and strong vs. weak polynomial time
textbook chapter: appendix A, continued

Lecture 5 (9/10/13)
covered material: minimum-cost spanning trees: Kruskal's and Prim's algorithms, the cut property of MSTs
textbook chapter: chapter 2.1

Lecture 6 (9/12/13)
covered material: LP relaxation for MSTs, Edmond's theorem that MST solution is LP's OPT
textbook chapter: chapter 2.1 continued
other: problem set 1 given out

Lecture 7 (9/17/13)
covered material: shortest path problem, Ford's algorithm, connection to LP duality
textbook chapter: chapter 2.2

Lecture 8 (9/19/13)
covered material: path packing, integral/non-interal max-flow, min-cut max-flow theorem
textbook chapter: chapters 3.1 and 3.2

Lecture 9 (9/24/13)
covered material: Ford-Fulkerson and Edmonds-Karp algorithms, König's theorem via flow-cut duality
textbook chapter: chapter 3.2 continued, chapter 3.3

Lecture 10 (9/26/13)
covered material: finding optimal closures, Gale's flow feasibility theorem
texbook chapter: chapter 3.3 continued

Lecture 11 (10/1/13)
covered material: min-cut in undirected graphs, node-identification and Karger's random contraction algorithms
textbook chapter: chapter 3.5

Lecture 12 (10/3/13)
covered material: multiterminal cuts and Gomory-Hu trees
textbook chapter: chapter 3.5 continued
other: problem set 2 given out

Lecture 13 (10/8/13)
covered material: min-cost flow problem, its generality, LP primal and dual, charactarization of LP optimiality
textbook chapter: chapter 4.1

Lecture 14 (10/10/13)
covered material: Kantorovich's augmenting circuits algorithm, discussion of improvement by Goldberg-Tarjan
textbook chapter: chapter 4.1 continued, chapter 4.2

Lecture 15 (10/15/13)
covered material: flows for bipartite matchings, matchings in general graphs, augmenting path theorem of matchings
textbook chapter: chapter 5.1

Lecture 16 (10/17/13)
covered material:the Tutte-Berge formula and Tutte's matching theorem
textbook chapter: chapter 5.1 continued

Lecture 17 (10/22/13)
covered material: alternating trees, bipartite perfect matchings via tree frustration
textbook chapter: chapter 5.2

Lecture 18 (10/24/13)
covered material: Edmonds's blossom algorithm, maximum matchings, algorithmic proof of the Tutte-Berge formula
textbook chapter: chapter 5.2 continued
other: presentation instructions given out and website announced

Lecture 19 (10/29/13)
covered material: matrix tree theorem and its generalization to weighted graphs (guest lecture by Prof. Brian Ziebart)
refrence: see these notes by Douglas B. West

Lecture 20 (10/31/13)
covered material: introduction to the traveling salesman problem, heuristics, Christophides's approximation algorithm
textbook chapter: chapter 7.1, chapter 7.2

Lecture 21 (11/5/13)
covered material: 2-OPT/3-OPT TSP heuristics, Lin-Kernighan algorithm, IP/LP and the Miller-Tucker-Zemlin formulation
textbook chapter: chapter 7.2 continued, chapter 7.3
additional reference: Pataki's paper

Lecture 22 (11/7/13)
covered material: separation oracles and the Ellipsoid algorithm, application to min-cost arborescence
textbook chapter: chapter 6.8 and parts of chapter 6.1 and 6.2 for background
additional reference: Goemans's lecture notes

Lecture 23 (11/12/13)
covered material: matroids and the greedy algorithm, the forest, linear, and uniform matroids
textbook chapter: chapter 8.1
other: problem set 3 given out

Lecture 24 (11/14/13)
covered material: greedy charactarization of matroids, application of matroids to scheduling with deadlines
textbook chapter: chapter 8.1 continued
additional reference: Erickson's lecture notes
other: in-class final exam scheduled for 12/5/13

Lecture 25 (11/19/13)
student presentations: smoothed analysis of Simplex (Yi Huang) and online bipartite matching (Adam Lelkes)
references: Spielman-Teng and Karp et al.

Lecture 26 (11/21/13)
student presentation: solving convex programs by random walks (Lujia Wang)
reference: Bertsimas-Vempala

Lecture 27 (11/26/13)
student presentations: optimization for linear separators (Jeremy Kun) and balancing MSTs / SP trees (Daniel Braithwaite)
references: Platt and Khuller et al.

Lecture 28 (12/3/13)
student presentations: randomized linear-time MST (John Hardwick) and an SP algorithm with expected linear time (Li Ge)
references: Karger et al. and Goldberg