On this page, we will provide links to papers we are discussing and a schedule for the in-class presentations.
September 5: Gagan Goel
September 12: Parikshit Ram, A Combinatorial, Primal-Dual approach to Semidefinite Programs A Combinatorial, Primal-Dual approach to Semidefinite Programs, by Sanjeev Arora & Satyen Kale, STOC 2007
September 19: Carl Yerger, Online Primal-Dual algorithms for maximizing ad-auctions revenue, Niv Buchbinder, Kamal Jain, Joseph Naor.
September 26: Kate Abercrombie, Primal-Dual Algorithms for QoS Multimedia Multicast, G. Calinescu, C.G. Fernandes, I.I. Mandoiu, A. Olshevsky, K. Yang, A. Zelikovsky
October 3: Shaudi Hosseini, Primal-Dual Schema for Capacitated Covering Problems, Tim Carnes and David Shmoys
October 8: Ashish Sangwan, Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach, Niv Buchbinder and Joseph Naor, FOCS 2006
October 10: Luke Postle, Online Primal-Dual algorithms for covering and packing problems Niv Buchbinder, Joseph (Seffi) Naor.
October 17: Pushkar Tripathi, A Primal-Dual Approximation Algorithm for Partial Vertex Cover: Making Educated Guesses Julian Mestre
October 24 : Shiva Kintali The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema , Mohammad Taghi Hajiaghayi, Kamal Jain
October 31: Sameer Indarapu, A 3-approximation for the minimum tree spanning k vertices, Naveen Garg
November 7: Murtaza
November 14: Lei Wang, Applications of Approximation Algorithms to Cooperative Games, Kamal Jain and Vijay Vazirani
November 21: Yorgos Amanatidis, Online Make-to-Order Joint Replenishment Model: Primal Dual Competitive Algorithms, by N. Buchbinder, T. Kimbrel, R. Levi, K. Makarychev, M. Sviridenko.
December 5: Arash Asadi, Primal-dual meets local search: Approximating MST's with nonuniform degree bounds J. Konemann and R. Ravi
Additional talk: Vishal Surana, Group Strategyproof Mechanisms via Primal-Dual Algorithms Martin Pal, Eva Tardos