Photo  

EECS 495: Approximation Algorithms

Instructor: Konstantin Makarychev

When: Spring 2017, MW 11:00-12:20, Room Tech F281

What: This course studies approximation algorithms – algorithms that are used for solving hard optimization problems. Such algorithms find approximate (slightly suboptimal) solutions to optimization problems in polynomial time. Unlike heuristics, approximation algorithms have provable performance guarantees: they have bounds on the running time and on the quality of the obtained solutions. In this course, we will introduce various algorithmic techniques used for solving optimization problems such as greedy algorithms, local search, dynamic programming, linear programming (LP), semidefinite programming (SDP), LP duality, randomized rounding, and primal-dual analysis.

Prerequisites: The course assumes background in basic probability theory and discrete mathematics. Key mathematical concepts will be reviewed before they are used.

Recommended texts

  • “Approximation Algorithms” by Vijay Vazirani.
  • “The Design of Approximation Algorithms” by David Williamson and David Shmoys. A copy of this book is available online (http://www.designofapproxalgs.com/book.pdf).

Homework

  1. Monday, April 10: Problem Set #1 due Wednesday, April 19, Problem Set #1.
  2. Monday, May 1: Problem Set #2 due Wednesday, May 10, Problem Set #2.
  3. Monday, May 15: Problem Set #3 due Monday, May 22, Problem Set #3.
  4. Wednesday, May 22: Problem Set #4 due Monday, May 31, Problem Set #4.

Schedule

  1. Monday, March 22: Introduction to Approximation Algorithms. Travel Salesperson Problem (the Christofides 3/2-approximation algorithm). Set Cover (log n approximation).
  2. Wednesday, March 29: Knapsack (2 approximation and PTAS).
  3. Monday, April 3: Bin Packing (2 approximation and PTAS). Makespan Scheduling on identical machines (4/3 approximation and PTAS).
  4. Wednesday, April 5: Scheduling with precedence constraints (Graham's 2-approximation algorithm). Clustering. k-center (2 approximation). k-means. Lloyd’s algorithm.
  5. Monday, April 10: Review of previous lectures. k-means++ (O(log k) approximation).
  6. Wednesday, April 12: k-means++ (O(log k) approximation).
  7. Monday, April 17: Local Search. k-median (5 approximation).
  8. Wednesday, April 19: Correlation Clustering (3 approximation)
  9. Monday, April 24: Linear Programming (LP). Set Cover. CPLEX vs Greedy Algorithm Demo.
  10. Wednesday, April 26: Vertex Cover. LP Duality (part I).
  11. Monday, May 1: LP Duality (part II). Examples. Min s-t Cut/Max Flow.
  12. Wednesday, May 3: Integrality of min s-t cuts. Multiway Cut (2 & 1.5 approximations)
  13. Monday, May 8: Multicut (log n approximation). Padded Decomposition.
  14. Wednesday, May 10: Embeddings into Trees & Random Trees. Applications.
  15. Monday, May 15: Sparsest Cut. Balanced Cut. LP Relaxation for the problems.
  16. Wednesday, May 17: Embeddings into L1. O(log n) approximation for Sparsest Cut. SDP Relaxation for Sparsest Cut.
  17. Monday, May 22: Graph Laplacian. Cheeger's Inequality. Max Cut.
  18. Wednesday, May 24:Workshop on Beyond Worst-Case Analysis (no class)
  19. Monday, May 29: Memorial Day (no class)
  20. Wednesday, May 31: Coloring. Combinatorial Algorithm. SDP algorithm.