CombOpt Reading Group

The purpose of our reading group is for students to learn new things, to learn how to present research to their peers, and to possibly pick up a research question or two in the process.

Each month or two we have a new topic of combinatorial optimization.



When:
Fridays, 1:00pm-3:00pm
Where:
MC 5479


To stay up to date please subscribe to our mailing list here. Please do not hesitate to contact Leanne Stuive, Justin Toth, Sharat Ibrahimpur or Kanstantsin Pashkovich in case you have any questions or suggestions.



Current Topic


Topic: Clustering.

12 Oct 2018
Chaitanya Swamy

Overview and LP rounding for uncapacitated facility location.


19 Oct 2018
Hao Sun

Primal dual for facility location, Lagrangian relaxation technique for k-median.


26 Oct 2018
Zishen Qu

Local search for uncapacitated facility location, capacitated facility location, k-median.


2 Nov 2018
Sharat Ibrahimpur

"Approximating k-Median via Pseudo-Approximation", 2013
by Shi Li and Ola Svensson


9 Nov 2018
(MC 5417)
Thomas Baxter

"Approximate Clustering without the Approximation", 2009
by Maria-Florina Balcan, Avrim Blum and Anupam Gupta


16 Nov 2018
Adam Brown

"Stability Yields a PTAS for k-Median and k-Means Clustering", 2010
by Pranjal Awasthi, Avrim Blum and Or Sheffet


23 Nov 2018
Akshay Ramachadran

"On the Local Structure of Stable Clustering Instances", 2017
by Vincent Cohen-Addad and Chris Schwiegelshohn


30 Nov 2018
Sharat Ibrahimpur

Ordered k-median.




Past Topics


Topic: Discrepancy.


13 Jan 2017
Kanstantsin Pashkovich

"“Integer-making” theorems", 1981
by József Beck and Tibor Fiala
Beck-Fiala Theorem can also be found in Chapter 4, "Geometric Discrepancy", Jiří Matoušek. This book is available online through UWaterloo Library.


20 Jan 2017
Sanchit Kalhan

"Roths estimate of the discrepancy of integer sequences is nearly sharp", 1981
by József Beck
Partial Coloring Lemma can also be found in Chapter 4, "Geometric Discrepancy", Jiří Matoušek. This book is available online through UWaterloo Library.


27 Jan 2017
Sina Rezazadeh

"Six standard deviations suffice", 1985
by Joel Spencer
Entropy Method and Spencer's Theorem can also be found in Chapter 4, "Geometric Discrepancy", Jiří Matoušek. This book is available online through UWaterloo Library.


03 Feb 2017
Julian Romero

"Constructive algorithms for discrepancy minimization", 2010
by Nikhil Bansal


10 Feb 2017
Ahmad Abdi

"Constructive discrepancy minimization by walking on the edges", 2012
by Shachar Lovett and Raghu Meka


17 Feb 2017
Mehdi Karimi

"An algorithm for Komlós conjecture matching Banaszczyk's bound", 2016
by Nikhil Bansal, Daniel Dadush, Shashwat Garg


24 Feb 2017
Nathan Lindzey

"Constructive Discrepancy Minimization for Convex Sets", 2014
by Thomas Rothvoss
Here is the talk Constructive Discrepancy Minimization for Convex Sets by Thomas Rothvoss.


3 Mar 2017
André Linhares

"The entropy rounding method in approximation algorithms", 2012
by Thomas Rothvoss


10 Mar 2017
This Friday we have no talks. However if you want to watch a talk on Discrepancy, here is a recent talk by Nikhil Bansal "Dicrepancy beyond Partial Colorings".

Topic: Ramanujan Graphs and Interlacing Families.


17 Mar 2017
Maxwell Levit

"Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees", 2013
by Adam Marcus, Daniel A. Spielman, Nikhil Srivastava
Ramanujan graphs, 2-lifts, spectral expansions and graph expansions will be defined. We will see Theorems of Heilmann and Lieb and Theorems of Godsil on matching polynomials.


24 Mar 2017
Leanne Stuive

"Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees ", 2013
by Adam Marcus, Daniel A. Spielman, Nikhil Srivastava
We will see core results on interlacing polynomials and stable polynomials.


31 Mar 2017
Mehdi Karimi

"Twice-Ramanujan Sparsifiers", 2014
by Joshua Batson, Daniel A. Spielman, Nikhil Srivastava
For a better understanding of the "barrier functions" argument, please view the talk Graph Sparsification II: Barrier Functions and Rank-one Updates by Nikhil Srivastava.
Here are two further talks by Nikhil Srivastava: Graph Sparsification I: Sparsification via Effective Resistances and Graph Sparsification III: Interlacing Polynomials and Ramanujan Graphs of Every Degree. Please also take a look at the blog posts by Nikhil Srivastava, for example the post on Discrepancy, Graphs, and the Kadison-Singer Problem.


7 Apr 2017
David Wagner

"Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem", 2013
by Adam Marcus, Daniel A. Spielman, Nikhil Srivastava
An overview of results and applications.


14 Apr 2017
Good Friday. This Friday we have no talks.


21 Apr 2017
Question Session. We discuss questions related to the topics of this term.



Topic: Traveling Salesman.


5 May 2017
Laura Sanità

Classic results and overview of the results from the chosen papers.


15 May 2017
(Monday)
Matthew Buckley

"Approximating Graphic TSP by Matchings", 2011
by Tobias Mömke, Ola Svensson
Here is a talk by Naveen Garg Approximating Graphic TSP by Matchings.


19 May 2017
Justin Toth

"Shorter Tours by Nicer Ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs", 2012
by András Sebő, Jens Vygen


26 May 2017
André Linhares

"On the metric s-t path Traveling Salesman Problem", 2014
by Zhihan Gao


2 June 2017
Martin Groß

"Better s-t-Tours by Gao Trees", 2015
by Corinna Gottschalk, Jens Vygen
Here is a talk by Jens Vygen Reassembling trees for the traveling salesman, which leads up to the result of Corinna Gottschalk and Jens Vygen. Please, note that recently Frans Schalekamp, András Sebö, Vera Traub and Anke van Zuylen provided a short proof of the key structural result of Corinna Gottschalk and Jens Vygen.


9 June 2017
András Sebö

"The Salesman's Improved Paths: A 3/2+1/34 Approximation", 2016
by András Sebö, Anke van Zuylen
The algorithm, the main proof of the analysis and the intuition behind its ingredients will be explained, including the gain of using Gottschalk and Vygen's particular convex combination of spanning trees, and how finally Frans Schalekamp, András Sebő, Vera Traub and Anke van Zuylen in "Layers and matroids for the travelling salesman's paths" (April 2017) finally managed to use matroid union for a simple algorithmic proof of this particular convex combination.


16 June 2017
Quincy Lap-Kwan Lam

"Polynomial-Time Separation of a Superclass of Simple Comb Inequalities", 2006
by Lisa K. Fleischer, Adam N. Letchford and Andrea Lodi


23 June 2017
Questions and Discussion Session with Sylvia Boyd and András Sebö.


30 June 2017
IPCO break. This Friday we have no talks.


7 July 2017
Akshay Ramachadran

"An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem", 2010
by Arash Asadpour, Michel X. Goemans, Aleksander Madry, Shayan Oveis Gharan, Amin Saberi
Here is a talk by Shayan Oveis The Asymmetric Traveling Salesman Problem.


14 July 2017
Zhuan Khye Koh

"Approximating ATSP by Relaxing Connectivity", 2015
by Ola Svensson
Here is a talk by Ola Svensson Approximating ATSP by Relaxing Connectivity.


21 July 2017
SiGMa break. This Friday we have no talks.


28 July 2017
Sharat Ibrahimpur

"Constant Factor Approximation for ATSP with Two Edge Weights", 2015
by Ola Svensson, Jakub Tarnawski, László A. Végh


4 Aug 2017
Akshay Ramachadran and Julian Romero

"Effective-Resistance-Reducing Flows, Spectrally Thin Trees, and Asymmetric TSP", 2014
by Nima Anari, Shayan Oveis Gharan
The talk does not assume any previous reading.
Further reading: Please take a look at the Nikhil Srivastava's blog Discrepancy, Graphs, and the Kadison-Singer Problem. Please also take a look at the course Recent Developments in Approximation Algorithms by Shayan Oveis Gharan. In Lectures 18 and 19 of this course, the results from the above paper were presented.



Topic: Stable Polynomials, Hyperbolic Polynomials and Optimization.


10 Jan 2018
(Wednesday,
1:00 pm)
Leanne Stuive

"Hyperbolic Programs, and Their Derivative Relaxations", 2006
by James Renegar
Further reading: Please take a look at the lecture notes for the course The Geometry of Polynomials in Algorithms, Combinatorics, and Probability (Lecture 11) taught by Nikhil Srivastava and the lecture notes for the course Algebraic Techniques and Semidefinite Optimization (Lecture 7) taught by Pablo Parrilo. Here is the thesis of Tor Myklebust "Geometry of convex sets arising from hyperbolic polynomials". Here are "Notes on Hyperbolicity Cones" by Petter Brändén.


12 Jan 2018
Leanne Stuive

"Hyperbolic Programs, and Their Derivative Relaxations", 2006
by James Renegar


19 Jan 2018
Akshay Ramachadran

"Multivariate stable polynomials: theory and applications", 2011
by David Wagner


26 Jan 2018
Akshay Ramachadran

"Multivariate stable polynomials: theory and applications", 2011
by David Wagner


2 Feb 2018
Sina Rezazadeh

"Hyperbolic Polynomials and Convex Analysis", 2001
by Heinz H. Bauschke, Osman Güler, Adrian S. Lewis, Hristo S. Sendov


9 Feb 2018
Stefan Sremac

"The Lax Conjecture Is True", 2005
by Adrian S. Lewis, Pablo A. Parrilo, Motakuri V. Ramana


16 Feb 2018
Julian Romero

"Exponential lower bounds on spectrahedral representations of hyperbolicity cones", 2017
by Prasad Raghavendra, Nick Ryder, Nikhil Srivastava, Benjamin Weitz


23 Feb 2018
Reading Week. This Friday we have no talks.


2 Mar 2018
Kanstantsin Pashkovich

"On Leonid Gurvits’s Proof for Permanents", 2010
by Monique Laurent and Alexander Schrijver


9 Mar 2018
(MC 5417)
Sharat Ibrahimpur

"Maximizing Determinants under Partition Constraints", 2015
by Aleksandar Nikolov and Mohit Singh
Here is the talk "Maximizing Sub-determinants and Connections to Permanents and Inequalities on Stable Polynomials" by Mohit Singh.


16 Mar 2018
Justin Toth

"Nash Social Welfare, Matrix Permanent, and Stable Polynomials", 2016
by Nima Anari, Shayan Oveis Gharan, Amin Saberi and Mohit Singh
Here is the talk "Nash Social Welfare, Matrix Permanent, and Stable Polynomials" by Nima Anari.


23 Mar 2018
Akshay Ramachadran

"A Generalization of Permanent Inequalities and Applications in Counting and Optimization", 2017
by Nima Anari and Shayan Oveis Gharan


30 Mar 2018
Good Friday. This Friday we have no talks.


Topic: Multiplicative Weight Updates.


1 Jun 2018
Julian Romero

Multiplicative Weight Updates as Mirror Descent.


8 Jun 2018
Zhuan Khye Koh

Weighted majority.


15 Jun 2018
Justin Toth

"Randomized Rounding without Solving the Linear Program", 1995
by Neal E. Young


22 Jun 2018
Jochen Koenemann

Packing and covering LP's.


29 Jun 2018
ISMP 2018. This Friday we have no talks.


6 Jul 2018
ISMP 2018. This Friday we have no talks.


13 Jul 2018
Akshay Ramachandran

Entropy, information and other interpretations.


20 Jul 2018
Sharat Ibrahimpur

"Nearly Linear-Time Approximation Schemes for Mixed Packing/Covering and Facility-Location Linear Programs", 2014
by Neal E. Young

"Near-linear time approximation schemes for some implicit fractional packing problems", 2017
by Chandra Chekuri and Kent Quanrud


27 Jul 2018
Sina Rezazadeh

Matrix multiplicative weight updates.


3 Aug 2018
Hong Zhou

"Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates", 2015
by Zeyuan Allen-Zhu, Zhenyu Liao, Lorenzo Orecchia