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.
9. Problem Set 8: Due December 11. Late days cannot be used for this homework.

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. (Dec 04) Pricing: Gross-Substitutes, Single Minded Valuations (Sec 11.7, 11.2)
12. (Dec 07) Pricing: Maximizing Revenue
13. (Dec 11) Pricing: Combinatorial Walrasian Equilibrium, Sequential Buyer Arrival
Final Exam on Monday, Dec 18, at 8:00am