Class Schedule -- Approximation Algorithms

Fall 2017
(Subject to change at any time)


Homeworks assigned:

  1. Problem Set 1: Due September 14.
  2. Problem Set 2: Due September 25. Note that, as with all future homeworks, you are allowed to turn in one copy of the homework for each pair of students.
  3. Problem Set 3: Due October 2.
  4. Midterm Exam: Due October 10. This exam is individual work, so please do not talk to others about it or use any resources other than the class textbook.
  5. Problem Set 4: Due October 19.
  6. Problem Set 5: Due October 30.
  7. Problem Set 6: Due November 9.
  8. Problem Set 7: Due November 27.

Lectures

Part I: Here the section numbers refer to Williamson/Shmoys: The Design of Approximation Algorithms.

  1. (Aug 31) Introduction: Vertex Cover, TSP (Sec 2.4)
  2. (Sep 07) Introduction to Linear Programming (Appendix A, Sec 4.3)
  3. (Sep 11) LP-Rounding: Set Cover (Sec 1.2-1.3, 1.7)
  4. (Sep 14) LP-Rounding: MAX-SAT (Sec 5.1, 5.4-5.6)
  5. (Sep 18) LP-Rounding: Minimizing Congestion (Sec 5.10-5.11)
  6. (Sep 21) LP-Duality and Primal-Dual Algorithms (Appendix A, Sec 7.1)
  7. (Sep 25) Primal-Dual: Shortest Path (Sec 7.3)
  8. (Sep 28) Primal-Dual: Steiner Forest (Sec 7.4)
  9. (Oct 02) Cuts and Metrics: Multicut (Sec 8.3)
  10. (Oct 05) Cuts and Metrics: Multiway Cut (Sec 8.1-8.2)
  11. (Oct 10) Intro to Semidefinite Programming (SDP), Max-Cut (Sec 6.1-6.2)
  12. (Oct 12) SDP Rounding: Max 2SAT
  13. (Oct 16) SDP Rounding: Correlation Clustering (Sec 6.4)
  14. (Oct 19) Greedy Algorithms: Set Cover (Sec 1.6)
  15. (Oct 23) Greedy Algorithms: Submodular functions/Max Coverage, k-Center (Sec 2.5, 2.2)
Part II: Here the section numbers refer to Nisan/Roughgarden/Tardos/Vazirani: Algorithmic Game Theory.
  1. (Oct 26) Class canceled, no lecture on this day
  2. (Oct 30) Introduction to Game Theory (Sec 1.1-1.3)
  3. (Nov 02) Game Theory: Network Formation Games, Congestion Games, and Potential Games (Sec 17.1-17.2, 19.3)
  4. (Nov 06) Game Theory: Selfish Routing (Ch 18)
  5. (Nov 09) Game Theory: Price of Anarchy in Smooth Games (Roughgarden)
  6. (Nov 13) Game Theory: Utility Games (Sec 19.4)
  7. (Nov 16) Game Theory: Local Connection Game (Sec 19.2)
  8. (Nov 20) Class canceled, no lecture on this day
  9. (Nov 27) Introduction to Markets and Pricing (Sec 11.1, 11.3)
  10. (Nov 30) Pricing: Maximizing Social Welfare and Walrasian Equilibrium (Sec 11.3, 11.5-11.7)
  11. (Dec 04) Pricing: Single Minded Valuations (Sec 11.2)
  12. (Dec 07) Pricing: Maximizing Revenue
  13. (Dec 11) Auctions and Mechanism Design (Sec 9.1, 9.3-9.6)
Final Exam on Monday, Dec 18, at 8:00am