General
Information
Course
Website: http://www.math.uwaterloo.ca/~harvey/RG/
Lecture
Time: Tuesdays, 46pm
Lecture
Room: MC 5136 (except
09/22)
Organizers: Nick Harvey, Jochen Konemann
Topics: This fall we
will read papers from recent and upcoming conferences. Our focus is on papers
relating to combinatorial optimization, mathematical programming, network
design, graph algorithms, algorithmic game theory, discrete probability, etc.
Participation: This term
there will be no course credit for participation, but reading papers is an
important aspect of being an active researcher. We strongly encourage all
graduate students working in related areas to attend and to give talks! To join the mailing list
please visit this link, and to
sign up to give a talk please email
Nick.
Schedule

Date 
Presenter 
Paper 
Authors 
1. 
09/22 
Deeparnab Chakrabarty 
Chakrabarty, Chuzhoy, Khanna 

2. 
09/29 
Jochen Konemann 
Improved
Approximation Algorithms for PrizeCollecting Steiner Tree and TSP 
Archer,
Bateni, Hajiaghayi,
Karloff 
3. 
10/06 
Marcus Shea 
An O(k^3
log n)Approximation Algorithm for VertexConnectivity Survivable Network
Design 
Chuzhoy, Khanna 
4. 
10/13 
David Pritchard 
Polymatroid Intersection, Submodular
Flows, and Lattice Polyhedra by Uncrossing 
Misc. 
5. 
10/20 
Bundit Laekhanukit 
Chakraborty, Chuzhoy, Khanna 

6. 
10/27 



7. 
11/03 
Nick Harvey 
A Simple
Combinatorial Algorithm for Submodular Function
Minimization 
Iwata,
Orlin 
8. 
11/10 
Joseph Cheriyan 
Kortsarz, Nutov 

9. 
11/17 
David Pritchard 
Hardness
of the undirected edgedisjoint paths problem. Notes. 
Andrews,
Zhang 
10. 
11/24 
Hadi Minooei 
Limits on the
Social Welfare of MaximalInRange Auction Mechanisms 
Buchfuhrer, Umans 
11. 
12/01 



Some
Suggested Papers
STOC
2009
·
Moser.
A constructive proof of the Lovász local lemma
·
MathieuSinclair.
SheraliAdams relaxations of the matching polytope
·
BatsonSpielmanSrivastava. TwiceRamanujan
Sparsifiers.
·
CharikarMakarychevMakarychev. Integrality Gaps for SheraliAdams Relaxations
·
Roughgarden.
Intrinsic Robustness
of the Price of Anarchy
·
GuptaKumar. A ConstantFactor
Approximation for Stochastic Steiner Forest
·
KleinbergPiliourasTardos. Multiplicative updates outperform
generic noregret learning in congestion games
·
GuptaKrishnaswamyRavi.
Online and
Stochastic Survivable Network Design
SOCG 2009
·
EisenbrandHähnleRothvoß. Diameter of
Polyhedra: Limits of Abstraction
FOCS
2009
·
IwataNagano.
Submodular Function Minimization under Covering Constraints
·
BansalWilliams.
Regularity Lemmas and Combinatorial
Algorithms
·
Vondrak.
Symmetry
and approximability of submodular
maximization problems
·
MadryKelner.
Faster
generation of random spanning trees
·
Kannan.
A new probability inequality using
typical moments and concentration results
·
Sherman.
Breaking the Multicommodity
Flow Barrier for sqrt(log(n))Approximations to
Sparsest Cut
·
ChakrabartyChuzhoyKhanna. On
Allocating Goods to Maximize Fairness
·
ArcherBateniHajiaghayiKarloff. Improved Approximation Algorithms for
PrizeCollecting Steiner Tree and TSP
·
ChuzhoyKhanna.
An O(k^3
log n)Approximation Algorithm for VertexConnectivity Survivable Network
Design
·
MontanariSaberi.
Convergence to
Equilibrium in Local Interaction Games
SODA
2010
·
AsadpourGoemansMadryOveis GharanSaberi.
An O(log n/log log n)Approximation Algorithm for the Asymmetric Traveling
Salesman Problem
·
FriggstadSalavatiyouSvitkina. Asymmetric Traveling
Salesman Path and Directed Latency Problems
·
ChanLau.
On linear and semidefinite programming relaxations
for hypergraph matching
·
ChandrasekaranGoyalHaeupler. Deterministic Algorithms for the Lovasz Local Lemma
·
GuptaKrishnaswamyRavi. Tree embeddings for 2EC network design.
·
OlverShepherd.
Approximability
of Robust Network Design
·
ChalermsookChuzhoy.
Resource Minimization for Fire Containment
·
EisenbrandHaehnlePalvolgyiShmonin.
Testing additive integrality gaps
·
ChekuriShepherdWeibel. FlowCut Gaps for Integer and Fractional Multiﬂows
·
GrandoniKrystaVentre.
Utilitarian Mechanism Design for MultiObjective Optimization
·
AzarDevanurJainRabani. Monotonicity in Bargaining Networks