The linear algebra of linear programs
The ellipsoid algorithm, embeddings into Euclidean space
Coloring 3-colorable graphs
Handouts (homework) for course.
Handout 1 (14 November 2018):
Vertex Cover and Set Cover
Handout 2 (28 November 2018):
Greedy algorithms
Handout 3 (12 December 2018):
Dynamic programming, local search.
Handout 4 (26 December 2018):
Deterministic rounding of LPs.
Handout 5 (9 January 2019):
Randomized rounding of LPs.
Handout 6 (30 January 2019):
Randomized rounding and SDPs.
If you find errors in handouts, please let me know.
Take home exam (20 February 2019):
Hand in by 2pm Feb 27.
Clarifications for the exam (24 February 2019).
Feedback Vertex Set (March 27, April 3, 2019).
Metric Facility Location (April 3-10, 2019).
Handouts (homework) for course.
Handout 1 (10 April 2019):
Metric facility location.
Handout 2 (15 May 2019):
Multiway cut and multi-cut.
Handout 3 (19 June 2019):
Metric embeddings.
Handout 4 (17 July 2019):
Final exam.