CMPT 881 - Randomized and Approximation Algorithms - Spring 2019

Course outlines:
Course Instructor: Igor Shinkar
Time: Tu, Th 11:30 AM – 12:50 PM
Location: AQ 5037
Office Hours: Schedule an appointment via email (Igor)
Discussion forum:

Course Description

This is a graduate-level course in approximation and randomized algorithms. Many discrete optimization problems arising in theory and practice turn out to be NP-hard, and thus optimal solutions cannot be computed efficiently unless P=NP. One approach to deal with this situation is to design approximation algorithms, i.e., efficient algorithms that are guaranteed to return a near-optimal solution. Randomized algorithms are another powerful and widely used approach to tackle problems for which efficient deterministic algorithms are not known. The objective of this course is to expose students to techniques in approximation and randomized algorithms.


There are no formal prerequisites, but the students should be comfortable with basic probability, linear algebra, and algorithms.

Standard books for reference

- The Design of Approximation Algorithms David P. Williamson and David B. Shmoys, Cambridge University Press, 2011
- Randomized Algorithms Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press, 1995

Related courses

- Lap Chi Lau's course notes
- Anna Karlin's course notes
- Luca Trevisan's course notes


Completing the course requires
  • regular attendance and participation,
  • light homework assignments,
  • final project.


Lecture 1 - January 3, 2019 A sample of approximation algorithms
* 2-approximation algorithm for Vertex Cover in polynomial time
* 1.99-approximation algorithm for Vertex Cover in time 1.1n

A sample of randomized algorithms
* Computing the area of a unit circle
* Freivalds' algorithm for verifying matrix multiplication

Lecture 2 - January 8, 2019 Karger's min-cut algorithm
Communication complexity: checking equality of two strings
Random matrices generate good codes.

Lecture 3 - January 10, 2019 Some basic probability facts
* Linearity of expectation
* Concentration inequalities

Satisfying 7/8-fraction of clauses in a 3-CNF formula

Lecture 4 - January 15, 2019 Satisfying 7/8-fraction of clauses in a 3-CNF formula deterministically
Discrepancy using Chernoff bound
ln(n)-approximation for Set Cover

Lecture 5 - January 17, 2019 Algorithms for approximating the clique problem

Lecture 6 - January 22, 2019 Solving Hamiltonian path using a dynamic algorithm.
Finding a path of length O(log(n)) using color coding.

Lecture 7 - January 24, 2019 The traveling salesman person problem.
2-approximation for metric TSP.
Christofides' algorithm: 1.5-approximation for metric TSP.
log(n)-approximation for asymmetric TSP.

Lecture 8 - January 29, 2019 Polynomial identity testing: the Schwartz--Zippel lemma
Finding a perfect matching in a bipartite graph

Lectures 9 - January 31, 2019 Finding a minimum weight perfect matching in a bipartite graph

Lecture 10 - February 5, 2019 Linear Programming: simple examples.
Fourier-Motzkin elimination.
Basic feasible solution.

Lecture 11 - February 7, 2019 Beck-Fiala theorem.
Duality in linear programming.

Lecture 12 - February 14, 2019 The weighted vertex cover problem

Lecture 13 - February 26, 2019 Semidefinite programming
0.878-approximation algorithm for max-cut (Goemans-Williamson)

Lecture 14 - February 28, 2019 Coloring 3-colorable graphs
Wigderson's algorithm
SDP based algorithm (Karger, Motwani, Sudan)

Lecture 15 - March 5, 2019 Coloring 3-colorable graphs using SDP (cont.)
Property testing: first example

Lecture 16 - March 12, 2019 Linearity testing
Fourier analysis of Boolean functions

Lecture 17 - March 14, 2019 The PCP Theorem and hardness of approximation

Lecture 18 - March 19, 2019 Hardness of approximation for clique using the FGLSS reduction

Homework assignments

Due to Thursday, February 7, 2019 Assignment 1

Due to Thursday, March 7, 2019 Assignment 2

Due to Thursday, March 28, 2019 Assignment 3

Class presentations

March 26, 2019 Speaker: Anurag Sanyal
Approximating Maximum Clique by Removing Subgraphs

Speaker: Amirhosein Kazeminia
Testing triangle freeness in dense graphs

March 28, 2019 Speaker: Fatemeh Hasiri
Finding Hidden Cliques in Linear Time with High Probability

Speaker: Mona Mehdizadeh
Sublinear Algorithms for (Δ+1) Vertex Coloring

April 2, 2019 Speaker: Akbar Rafiey
On the Beck-Fiala Conjecture for Random Set Systems

Speaker: Zhenjian Lu
On Khot's unique games conjecture

April 4, 2019 Speaker: Neda Shokraneh
Unique Games on Expanding Constraint Graphs are Easy

Speaker: Sophie Oh
Expander Flows, Geometric Embeddings and Graph Partitioning