General
Information
Course
Website: http://www.math.uwaterloo.ca/~harvey/RG/
Lecture
Time: Tuesdays, 4-6pm
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 Prize-Collecting Steiner Tree and TSP |
Archer,
Bateni, Hajiaghayi,
Karloff |
|
3. |
10/06 |
Marcus Shea |
An O(k^3
log n)-Approximation Algorithm for Vertex-Connectivity 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 edge-disjoint paths problem. Notes. |
Andrews,
Zhang |
|
10. |
11/24 |
Hadi Minooei |
Limits on the
Social Welfare of Maximal-In-Range Auction Mechanisms |
Buchfuhrer, Umans |
|
11. |
12/01 |
|
|
|
Some
Suggested Papers
STOC
2009
·
Moser.
A constructive proof of the Lovász local lemma
·
Mathieu-Sinclair.
Sherali-Adams relaxations of the matching polytope
·
Batson-Spielman-Srivastava. Twice-Ramanujan
Sparsifiers.
·
Charikar-Makarychev-Makarychev. Integrality Gaps for Sherali-Adams Relaxations
·
Roughgarden.
Intrinsic Robustness
of the Price of Anarchy
·
Gupta-Kumar. A Constant-Factor
Approximation for Stochastic Steiner Forest
·
Kleinberg-Piliouras-Tardos. Multiplicative updates outperform
generic no-regret learning in congestion games
·
Gupta-Krishnaswamy-Ravi.
Online and
Stochastic Survivable Network Design
SOCG 2009
·
Eisenbrand-Hähnle-Rothvoß. Diameter of
Polyhedra: Limits of Abstraction
FOCS
2009
·
Iwata-Nagano.
Submodular Function Minimization under Covering Constraints
·
Bansal-Williams.
Regularity Lemmas and Combinatorial
Algorithms
·
Vondrak.
Symmetry
and approximability of submodular
maximization problems
·
Madry-Kelner.
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
·
Chakrabarty-Chuzhoy-Khanna. On
Allocating Goods to Maximize Fairness
·
Archer-Bateni-Hajiaghayi-Karloff. Improved Approximation Algorithms for
Prize-Collecting Steiner Tree and TSP
·
Chuzhoy-Khanna.
An O(k^3
log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network
Design
·
Montanari-Saberi.
Convergence to
Equilibrium in Local Interaction Games
SODA
2010
·
Asadpour-Goemans-Madry-Oveis Gharan-Saberi.
An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling
Salesman Problem
·
Friggstad-Salavatiyou-Svitkina. Asymmetric Traveling
Salesman Path and Directed Latency Problems
·
Chan-Lau.
On linear and semidefinite programming relaxations
for hypergraph matching
·
Chandrasekaran-Goyal-Haeupler. Deterministic Algorithms for the Lovasz Local Lemma
·
Gupta-Krishnaswamy-Ravi. Tree embeddings for 2EC network design.
·
Olver-Shepherd.
Approximability
of Robust Network Design
·
Chalermsook-Chuzhoy.
Resource Minimization for Fire Containment
·
Eisenbrand-Haehnle-Palvolgyi-Shmonin.
Testing additive integrality gaps
·
Chekuri-Shepherd-Weibel. Flow-Cut Gaps for Integer and Fractional Multiflows
·
Grandoni-Krysta-Ventre.
Utilitarian Mechanism Design for Multi-Objective Optimization
·
Azar-Devanur-Jain-Rabani. Monotonicity in Bargaining Networks