C&O Reading Group

The C&O reading group is run by graduate students, post-docs and faculty. Currently we are meeting once per week. The main purpose of our meetings is letting people know what we are working on or what we find interesting in recent and classic publications. Our meetings are also appropriate for practice talks or presentations of ongoing research. E-mail reminders for our presentations are sent on a weekly basis, one day prior to our meetings. If you want to give a talk, or to be added to our mailing list, or if you have any comment, please contact the host of this webpage.

Some guidelines, and how we think of our reading group:

• Talks are usually 1.5 hours long. This may include a 5-10 mins break.
• Speakers are free to choose their topics. For this they may also consult our repository of interesting papers to read. Our focus though is on whatever touches on Algorithms or is relevant to Combinatorial Problems.
• Speakers do not assume any familiarity of the selected topic from the side of the audience. Presentations usually start with a high level exposition of the result, and finish with its technical contribution. At the end we try to have a 5-10 mins discussion of relevant open problems.
• Dates are assigned to speakers much in advance. Topics may not be announced till the last moment. If you choose though a paper from the repository, please announce your intention to avoid conflicts.

Fall 2011: Meetings will be held every Wednesday, at 4:30pm Thursday at 4:15pm (usually in IQC room MC5168). Please subscribe to our mailing list to receive reminders and last-moment change notifications.

Date	Speaker	Topic	Location
April 26, 2012	Zac Friggstad	“Improving Christofides' Algorithm for the s-t Path TSP” by An, Kleinberg, and Shmoys.	TBA
April 19, 2012	Nima Mousavi	TBA	TBA
April 12, 2012	Soroush Alamdari	TBA	TBA
April 5, 2012	Zhihan Gao	TBA	TBA
March 29, 2012	Fidel Barrera-Cruz	TBA	TBA
March 22, 2012	Marco Blanco	TBA	TBA
March 15, 2012	Isaac Fung	TBA	TBA
March 8, 2012	Hadi Minooei	TBA	TBA
March 1, 2012	Ahmad Abdi	TBA	TBA
February 16, 2012	Abbas Mehrabian	“Testing Properties of Directed Graphs: Acyclicity and Connectivity” by by Bender and Ron ICALP 2000 and RSA 2002	MC 5168 (IQC room)
February 8, 2012	Sara Ahmadian	“Constant Factor Approximation Algorithm forthe Knapsack Median Problem” By Amit Kumar (SODA12).	MC 5168 (IQC room)
February 1, 2012	Vinayak Pathak	"On Range Searching in the Group Model and Combinatorial Discrepancy." by Kasper Green Larsen (FOCS11)	MC 5168 (IQC room)
January 25, 2012	Leanne Stuive	"Edge-Disjoint Paths in Planar Graphs." Relevant reference: Séguin-Charbonneua,Shephard-FOCS 2011	MC 5168 (IQC room)
January 18, 2012	Nishad Kothari	"Width Parameters for Directed Graphs" Relevant references: Hunter-Kreutzer07, Kintali-Kothari-Kumar11.	MC 5168 (IQC room)
January 11, 2012	Devanshu Pandey	“Dueling Algorithms” by Immorlica, Kalai, Lucier, Moitra, Postlewaite, and Tennenhotz (STOC11)	MC 5168 (IQC room)
December 14, 2011	Costis Georgiou	“A tutorial on Lift-and-Project Systems”	MC 5168 (IQC room)
December 7, 2011	Leanne Stuive	“Improved Mincut and Maxflow in Planar Undirected Graphs” by Italiano, Nussbaum, Sankowski and Wulff-Nilsen (STOC11)	MC 5168 (IQC room)
November 30, 2011	Nima Mousavi	“Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs” by Goel, Kapralov and Khanna (STOC10)	MC 5168 (IQC room)
November 23, 2011	Soroush Alamdari	“Planar and Poly-Arc Lombardi Drawings” by Duncan, Eppstein, Goodrich, Kobourov and Löffler (Graph Drawing 2011)	MC 5168 (IQC room)
November 16, 2011	Zac Friggstad	"Santa Claus Schedules Jobs on Unrelated Machines" by Ola Svenssonn (STOC11)	MC 5168 (IQC room)
November 9, 2011	Abbas Mehrabian	"Min-Max Graph Partitioning and Small-Set Expansion" by Bansal, Feige, Krauthgamer, Makarychev, Nagarajan, Naor and Schwartz (FOCS11)	MC 5168 (IQC room)
November 2, 2011	Marco Blanco	“Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem” by Carnes and Shmoys (APPROX11)	MC 5168 (IQC room)
October 26, 2011	Fidel Barrera-Cruz	"Three-coloring triangle-free planar graphs in linear time" by Dvorak, Kawarabayashi and Thomas (SODA09)	MC 5168 (IQC room)
October 19, 2011	Hadi Minooei	"Towards Optimal Bayesian Algorithmic Mechanism Design" by Bei and Huang (SODA11)	MC 5168 (IQC room)
October 12, 2011	Malcolm Sharpe	“Transversals of d-Intervals” by Kaiser (Discrete & Computational Geometry, 1997)	MC 5168 (IQC room)
October 5, 2011	Malcolm Sharpe	“Jump Number of Two-Directional Orthogonal Ray Graphs” by Soto and Telha (IPCO11)	MC 5168 (IQC room)
September 21, 2011	Isaac Fung	“Approximating Graphic TSP by Matchings” by Mömke and Svensson (FOCS11)	MC 5168 (IQC room)
September 14, 2011	Costis Georgiou	“How bad is forming your own opinion?” by Bindel, Kleinberg and Oren (FOCS11)	MC 5168 (IQC room)
July 26, 2011	Abbas Mehrabian	"Constructive Algorithms for Discrepancy Minimization" by Nikhil Bansal.	MC 5168 (IQC room)
July 12, 2011	Malcolm Sharpe	"Matroid matching: the power of local search" by Lee, Sviridenko and Vondrak (STOC10)	MC 5168 (IQC room)
July 5, 2011	Fidel Barrera-Cruz	“On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs” by He and Zhang (SODA11)	MC 5168 (IQC room)
June 28, 2011	Jochen Könemann	“Set Cover with Ordered Replacement - Additive and Multiplicative Gaps” by Eisenbrand, Kakimura, Rothvoß, Sanita (IPCO11)	MC 5168 (IQC room)
June 21, 2011	Costis Georgiou	"On a one-dimensional problem concerning random space filling" by Renyi (Publ. Math. Inst. Hung. Acad. Sci., 1958)	MC 5168 (IQC room)
June 7, 2011	Marco Blanco	"The Matroid Median Problem" by Krishnaswamy, Kumar, Nagarajan, Sabharwal, Saha (SODA11).	MC 5168 (IQC room)
May 31, 2011	Soroush Hosseini	"Approximate range searching in higher dimension" by Chazelle, Liu and Magen (CGTA08).	MC 5168 (IQC room)
May 24, 2011	Hadi Minooei	“Multi-unit Auctions with Budget Limits” by Dobzinski, Lavi and Nisan (FOCS08).	MC5046A (Jim’s room)
May 17, 2011	Elyot Grant	“Tight lower bounds for the size of epsilon-nets” by Pach and Tardos (SoCG11).	MC5046A (Jim’s room)
May 10, 2011	Abbas Mehrabian	"Computing the Independence Number of Intersection Graphs" by Fox and Pach (SODA11).	MC5046A (Jim’s room)
May 3, 2011	Malcolm Sharpe	"Cohen and Nutov's Application of Zelikovsky's Greedy Heuristic to Tree Augmentation, with Matroid Generalization" Original work. Relevant references: Zelikovsky 1995, Cohen, Nutov 2011	MC5046A (Jim’s room)
April 18, 2011	Malcolm Sharpe	"A (1 + ln 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees with constant radius" by Cohen and Nutov (Manuscript 2011).	MC5046A (Jim’s room)
April 11, 2011	Hadi Minooei	"Multi-unit auctions with budget-constrained bidders" by Borgs, Chayes, Immorlica, Mahdian and Saberi (EC05).	MC5046A (Jim’s room)
April 4, 2011	Costis Georgiou	“On the Approximability of Budget Feasible Mechanisms" by Chen, Gravin and Lu (SODA11).	MC5046A (Jim’s room)
March 29, 2011	Abbas Mehrabian	"Faster generation of random spanning trees" by Kelner, and Madry (FOCS09).	MC5046A (Jim’s room)
March 22, 2011	Elyot Grant	"Some New APX-hardness results for Geometric Set Cover Problems" Original work. (jointly with Timothy Chan)	MC5046A (Jim’s room)
March 15, 2011	Krystal Guo	"Prizing on Paths: A PTAS for the Highway Problem" by Grandoni and Rothvoß (SODA11)	MC 5168 (IQC room)
March 8, 2011	Chaitanya Swamy	“From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions for Submodular Bidders" by Sughmi, Roughgarden and Yan (STOC11).	MC 5168 (IQC room)
February 29, 2011	Malcolm Sharpe	"Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures" by Chekuri, Vondrak, and Zenklusen. (FOCS 2010).	MC 5168 (IQC room)
February 15, 2011	Costis Georgiou	“An improved LP-based approximation for steiner tree” by Byrka, Grandoni, Rothvoß and Sanità (STOC11).	MC 5168 (IQC room)
February 8, 2011	Jochen Könemann	"Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound" by Chakrabarty, Koenemann and Pritchard (Operations Letters 2010)	MC 5168 (IQC room)
February 1, 2011	Costis Georgiou	“Fooling strong LP and SDP hierarchies for Vertex Cover” Relevant references: G., Magen, Tourlakis 2009, Benabbas, Chan, G., Magen 2010	MC 5168 (IQC room)