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