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. 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 a paper, please announce your intention to avoid conflicts.

Spring 2013: Meetings will be held every Wednesday at 4:15pm in IQC room MC5168.

Please subscribe to our mailing list to receive reminders and last-moment change notifications.

Date	Speaker	Topic
July 31, 2013	Ahmad Abdi	TBA
July 24, 2013	Sara Ahmadian	TBA
July 17, 2013	Srinivasan Arunachalam	TBA
July 10, 2013	Linda Farczadi	TBA
July 3, 2013	Harmony Zhan	TBA
June 26, 2013	Zhihan Gao	TBA
June 19, 2013	Zac Friggstad	“The Bounded-Regret Vehicle Routing Problem (BVRP)” Original work (Z. Friggstad and C. Swamy).
June 12 ,2013	Vinayak Pathak	"Reconfiguration problems: A survey" A survey based on [1].
June 5, 2013	Ehsan Ebrahimzadeh	"Sufficient conditions on existence of fix-free codes" A survey, based on [1],[2]
May 29, 2013	Elaheh Fata	"Approximation Algorithms for the Bottleneck Asymmetric Travelling Salesman Problem" by An, Kleinberg and Shmoys (APPROX10)
May 22, 2013	Seyed Saeed Rezaei	"Line-graphs of cubic graphs are normal" by Zsolt Patakfalvi (arXiv08)
May 15, 2013	Mohammad Shadravan	“Directed Steiner Tree and the Lasserre Hierarchy" by T. Rothvoß (arXiv12)
May 8, 2013	Ian Post	"Linear vs Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds" by Fiorini, Massar, Pokutta, Tiwary and de Wolf (STOC12)
May 1, 2013	Nishad Kothari	“K_4-free and prism-free planar matching covered graphs” Relevant papers [1], [2], [3], [4]
April 17, 2013	Sina Sadeghian	"The Diffusion of Networking Technologies" by Goldberg and Liu (SODA'13)
April 10, 2013	Zac Friggstad	"Approximating k-Median via Pseudo-Approximation" by Li and Svensson (manuscript)
April 3, 2013	Fidel Barrera-Cruz	"Morphing Planar Graph Drawings with a Polynomial Number of Steps" by Alamdari, Angelini, Chan, Di Battista, rati, Lubiw, atrignani, Roselli, Singla, Wilkinson (SODA13)
March 27, 2013	Jalaj Upadhyay	"Privacy and the Johnson-Linderstrauss Lemma" relevant papers [1], [2]
March 20, 2013	Andreas Feldmann	"Prize-collecting Steiner Problems on Planar Graphs" by Bateni, Chekuri, Ene, Hajiaghayi, Korula and Marx (SODA11)
March 13, 2013	Guru Prashanth	"Catch Them If You Can: How to Serve Impatient Users" by Cygan, Englert, Gupta, Mucha and Sankowski (ITCSC13)
March 6, 2013	Narges Simjour	"Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset" by R. Chitnis, M. Hajiaghayi, and D. Marx (SODA12)
February 27, 2013	Zhihan Gao	"Eight-Fifth Approximation for TSP Paths" by A. Sebö (To appear in IPCO 2013)
February 13, 2013	Vinayak Pathak	"Using partial cubes to find shortest paths in sublinear time" Related references [1], [2], [3], [4]
February 6, 2013	Sara Ahmadian	"Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching" by Devanur, Jain and Kleinberg (SODA13)
January 30, 2013	Linda Farczadi	"Balanced Outcomes in Social Exchange Networks" by Kleiberg and Tardos (STOC08)
January 23, 2013	Ahmad Abdi	From Pfaffian Orientations to Packing and Covering Related papers [1], [2], [3], [4], [5]
January 16, 2013	Venkatesh Raman	"A 4k^2 kernel for feedback vertex set" by Thomasse (ACM Transaction on Algorithms 2010)
December 13, 2012	Zhihan Gao	"Integrality gaps of linear and semi-definite programming relaxations for Knapsack" by Karlin, Mathieu, and Nguyen (IPCO'11)
December 6, 2012	Leanne Stuive	"A Constructive Version of Lehman's Theorem and Applications in Flow Problems" Thesis related subject.
November 29, 2012	Guru Prashanth	"Welfare and Profit Maximization with Production Costs" by Blum, Gupta, Mansour, and Sharma (FOCS11)
November 22, 2012	Andreas Feldmann	"Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations" by Goemans, Olver, Rothvoß and Zenklusen (FOCS12)
November 15, 2012	Sara Ahmadian	"A 5-approximation algorithm for capacitated facility location problem" by Bansal, Garg and Gupta (ESA12)
November 8, 2012	Olivier Durand de Gevigney	"Basic Packing of Arborescences" by Durand de Gevigney, Nguyen and Szigeti (arXiv12)
November 1, 2012	Linda Farczadi	"An efficient algorithm for nucleolus and prekernel computation in some classes of TU-games" by Faigle, Kern and Kuipers (Tech. Report 1998)
October 25, 2012	Sina Sadeghian	"Approximate k -MSTs and k -Steiner Trees via the Primal-Dual Method and Lagrangean Relaxation" by by Chudak, Roughagarden and Williamson (IPCO01)
October 18, 2012	Vinayak Pathak	"On a Linear Program for Minimum-Weight Triangulation" by Yousefi and Young (SODA12)
October 11, 2012	Nishad Kothari	"Matching Structure and the Matching Lattice" by Lovász (JCT Series B, 1987)
October 4, 2012	Devanshu Pandey	"Min-Max Tree Covers of Graphs" Talk will be based on "Improved Approximation Algorithms for the Min-Max Tree Cover and Bounded Tree Cover Problems" by Reza khani and Salavatipour. (APPROX11) , and his own research.
September 27, 2012	Abbas Mehrabian	"The hitting and cover times of random walks on finite graphs using local degree information" by Ikeda, Kubo and Yamashita (Theor. Comput. Sci. 2009)
September 20, 2012	Zac Friggstad	"Advances on Matroid Secretary Problems: Free Order Model and Laminar Case" by Patrick Jaillet, José A. Soto, Rico Zenklusen (arXiv12)
July 26, 2012	Hadi Minooei	"Optimal auctions with correlated bidders are easy" by Dobzinski, Fu and Kleinberg (STOC11)
July 19, 2012	Abbas Mehrabian	"Constructive Discrepancy Minimization by Walking on The Edges" by Lovett and Meka (FOCS12)
July 12, 2012	Ahmad Abdi	"Packing Odd Circuit Covers" by Abdi and Guenin (2012)
July 5, 2012	Nishad Kothari	"Directed Tree-width" by Johnsona, Robertsonb, Seymoura, and Thomasc (Journal of Combinatorial Theory 2001)
June 28, 2012	Sara Ahmadian	"A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems" by Cheung and Shmoys (APPROX11)
June 21, 2012	Leanne Stuive	"Matroidal Degree-Bounded Minimum Spanning Trees" by Zenklusen (SODA12)
June 14, 2012	Laura Sanita	"Extensions and limits to vertex sparsification" by Leighton and Moitra (STOC10)
June 7, 2012	Guru Prashanth	"One Tree Suffices: A Simultaneous O(1)-Approximation for Single-Sink Buy-at-Bulk" by Goel and Post (FOCS11)
May 31, 2012	Fidel Barrera-Cruz	"Graph Connectivities, Network Coding, and Expander Graphs" by Cheung, Lau and Leung (FOCS11)
May 24, 2012	Vinayak Pathak	"Flip Distance Between Two Triangulations of a Point-Set is NP-complete" by Lubiw and Pathak (Arxiv12)
May 17, 2012	Zhihan Gao	"A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs" by Safari and Salavatipour (SIAM J. Discrete Math. 25 (3): 1089-1102, 2011)
May 10, 2012	Costis Georgiou	"Subexponential Algorithms for Set-Cover" By Chlamtac, Friggstad and Georgiou (Arxiv12)
May 3, 2012	Devanshu Pandey	"Facility Location with Client Latencies: Linear Programming Based Techniques for Minimum Latency Problems" By Chakrabarty and Swamy, (IPCO11)
April 26, 2012	Zac Friggstad	"The Connected T-Join Problem in General Metrics" by Cheriyan, Friggstad and Gao. (2012)
April 19, 2012	Isaac Fung	"Capacitated Metric Labeling" by Andrews, Hajiaghayiy, Karloff and Moitra (SODA11)
April 12, 2012	Soroush Alamdari	"Min-Max Latency Walks" by Alamdari, Fata, Smith (Arxiv12)
March 29, 2012	Sahil Singla	"PTAS for Eucledian k-TSP and Orienteering Problems" This will be based on "The Orienteering Problem in the Plane Revisited" by Chen and Har-Peled, SIAM J. Comput. 38(1): 385-397 (2008)
March 22, 2012	Marco Blanco	“Bin Packing via Discrepancy of Permutations” by Eisenbrand, Pálvölgyi, Rothvoß (SODA11)
March 8, 2012	Hadi Minooei	“An impossibility result for truthful combinatorial auctions with submodular valuations” by Dobzinski, (STOC11)
March 1, 2012	Ahmad Abdi	“Packing Binary Clutters and the Cycling Conjecture” A survey. Relevant reference Seymour77
February 16, 2012	Abbas Mehrabian	“Testing Properties of Directed Graphs: Acyclicity and Connectivity” by Bender and Ron ICALP 2000 and RSA 2002
February 8, 2012	Sara Ahmadian	“Constant Factor Approximation Algorithm forthe Knapsack Median Problem” By Amit Kumar (SODA12).
February 1, 2012	Vinayak Pathak	"On Range Searching in the Group Model and Combinatorial Discrepancy." by Kasper Green Larsen (FOCS11)
January 25, 2012	Leanne Stuive	"Edge-Disjoint Paths in Planar Graphs." Relevant reference: Séguin-Charbonneua,Shephard-FOCS 2011
January 18, 2012	Nishad Kothari	"Width Parameters for Directed Graphs" Relevant references: Hunter-Kreutzer07, Kintali-Kothari-Kumar11.
January 11, 2012	Devanshu Pandey	“Dueling Algorithms” by Immorlica, Kalai, Lucier, Moitra, Postlewaite, and Tennenhotz (STOC11)
December 14, 2011	Costis Georgiou	“A tutorial on Lift-and-Project Systems”
December 7, 2011	Leanne Stuive	“Improved Mincut and Maxflow in Planar Undirected Graphs” by Italiano, Nussbaum, Sankowski and Wulff-Nilsen (STOC11)
November 30, 2011	Nima Mousavi	“Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs” by Goel, Kapralov and Khanna (STOC10)
November 23, 2011	Soroush Alamdari	“Planar and Poly-Arc Lombardi Drawings” by Duncan, Eppstein, Goodrich, Kobourov and Löffler (Graph Drawing 2011)
November 16, 2011	Zac Friggstad	"Santa Claus Schedules Jobs on Unrelated Machines" by Ola Svenssonn (STOC11)
November 9, 2011	Abbas Mehrabian	"Min-Max Graph Partitioning and Small-Set Expansion" by Bansal, Feige, Krauthgamer, Makarychev, Nagarajan, Naor and Schwartz (FOCS11)
November 2, 2011	Marco Blanco	“Primal-Dual Schema and Lagrangian Relaxation for the k-Location-Routing Problem” by Carnes and Shmoys (APPROX11)
October 26, 2011	Fidel Barrera-Cruz	"Three-coloring triangle-free planar graphs in linear time" by Dvorak, Kawarabayashi and Thomas (SODA09)
October 19, 2011	Hadi Minooei	"Towards Optimal Bayesian Algorithmic Mechanism Design" by Bei and Huang (SODA11)
October 12, 2011	Malcolm Sharpe	“Transversals of d-Intervals” by Kaiser (Discrete & Computational Geometry, 1997)
October 5, 2011	Malcolm Sharpe	“Jump Number of Two-Directional Orthogonal Ray Graphs” by Soto and Telha (IPCO11)
September 21, 2011	Isaac Fung	“Approximating Graphic TSP by Matchings” by Mömke and Svensson (FOCS11)
September 14, 2011	Costis Georgiou	“How bad is forming your own opinion?” by Bindel, Kleinberg and Oren (FOCS11)
July 26, 2011	Abbas Mehrabian	"Constructive Algorithms for Discrepancy Minimization" by Nikhil Bansal.
July 12, 2011	Malcolm Sharpe	"Matroid matching: the power of local search" by Lee, Sviridenko and Vondrak (STOC10)
July 5, 2011	Fidel Barrera-Cruz	“On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs” by He and Zhang (SODA11)
June 28, 2011	Jochen Könemann	“Set Cover with Ordered Replacement - Additive and Multiplicative Gaps” by Eisenbrand, Kakimura, Rothvoß, Sanita (IPCO11)
June 21, 2011	Costis Georgiou	"On a one-dimensional problem concerning random space filling" by Renyi (Publ. Math. Inst. Hung. Acad. Sci., 1958)
June 7, 2011	Marco Blanco	"The Matroid Median Problem" by Krishnaswamy, Kumar, Nagarajan, Sabharwal, Saha (SODA11).
May 31, 2011	Soroush Hosseini	"Approximate range searching in higher dimension" by Chazelle, Liu and Magen (CGTA08).
May 24, 2011	Hadi Minooei	“Multi-unit Auctions with Budget Limits” by Dobzinski, Lavi and Nisan (FOCS08).
May 17, 2011	Elyot Grant	“Tight lower bounds for the size of epsilon-nets” by Pach and Tardos (SoCG11).
May 10, 2011	Abbas Mehrabian	"Computing the Independence Number of Intersection Graphs" by Fox and Pach (SODA11).
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
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).
April 11, 2011	Hadi Minooei	"Multi-unit auctions with budget-constrained bidders" by Borgs, Chayes, Immorlica, Mahdian and Saberi (EC05).
April 4, 2011	Costis Georgiou	“On the Approximability of Budget Feasible Mechanisms" by Chen, Gravin and Lu (SODA11).
March 29, 2011	Abbas Mehrabian	"Faster generation of random spanning trees" by Kelner, and Madry (FOCS09).
March 22, 2011	Elyot Grant	"Some New APX-hardness results for Geometric Set Cover Problems" Original work. (jointly with Timothy Chan)
March 15, 2011	Krystal Guo	"Prizing on Paths: A PTAS for the Highway Problem" by Grandoni and Rothvoß (SODA11)
March 8, 2011	Chaitanya Swamy	“From Convex Optimization to Randomized Mechanisms: Toward Optimal Combinatorial Auctions for Submodular Bidders" by Sughmi, Roughgarden and Yan (STOC11).
February 29, 2011	Malcolm Sharpe	"Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures" by Chekuri, Vondrak, and Zenklusen. (FOCS 2010).
February 15, 2011	Costis Georgiou	“An improved LP-based approximation for steiner tree” by Byrka, Grandoni, Rothvoß and Sanità (STOC11).
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)
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