|
Computer Science 597B
Topics in Algorithms
|
Fall 2013
|
Course Summary
Study of current research in algorithms, focusing on optimization problems. Topics are drawn from applications of mathematical programming techniques, advances in spectral methods, fast approximate algorithms for flows and approaches to go beyond worst case analysis. Other topics may be included depending on the interests of the participants.
Students will read and present recent research papers.
Prerequisite: A graduate course in algorithms, or
equivalent mathematical maturity. Listeners and auditors are
welcome with prior permission.
Administrative Information
Lectures: Tue-Thu 3:00-4:20 Room 302, CS
Bldg.
Instructor: Moses Charikar: 305
CS Building - 258-7477 moses [AT] cs.princeton.edu
Piazza: We will use Piazza for class discussions and announcements. Sign up here:
https://piazza.com/princeton/fall2013/cos597/home
Graduate Coordinator: Melissa Lawson -
310 CS Building - 258-5387 mml [AT] cs.princeton.edu
Schedule
(Updated as the semester progresses.)
Sept 12: Interlacing Families I
Sept 17, 19: Twice-Ramanujan Sparsifiers
I followed the presentation of the proof in Assaf Naor's survey of the result and some of its applications:
http://arxiv.org/abs/1101.4324
Sept 24: Interlacing Families I cont.
Technical details of the proof: established results on real rootedness I claimed earlier via theory of real stable polynomials. Also introduced the results in Interlacing Families II.
Sept 26: Interlacing Families II.
Technical details of the proof. The interesting new component (relative to Interlacing Families I) is the argument they use to bound the value of the largest root of the expected characteristic polynomial they obtain. I described the multivariate barrier argument they use, which is a generalization of the barrier argument in the Batson-Spielman-Srivastava work.
Oct 1-3: Asymmetric TSP and thin trees
I'll switch gears slightly and talk about a couple of "older" papers not on the list
on the course webpage:
An O(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem,
A. Asadpour, M.X. Goemans, A. Madry, S. Oveis Gharan and A. Saberi,
http://math.mit.edu/~goemans/PAPERS/atsp-soda10.pdf
Dependent Randomized Rounding for Matroid Polytopes and Applications
Chandra Chekuri, Jan Vondrak, Rice Zenklusen
http://arxiv.org/abs/0909.4348
The first paper improves a nearly thirty year old O(log n) approximation for asymmetric TSP.
As we'll see, a certain notion of thin trees plays a central role in the algorithm - this is a certain kind of
sparsifier. The second paper gives a much simpler construction of thin trees than the original paper.
The approximation ratio of this algorithm is directly linked to the quality of thin trees one can construct.
Obtaining better constructions of such thin trees is a very interesting open problem.
Oct 8-10: Matrix concentration via pessimistic estimators
This week, Ankit will talk about this upcoming paper in SODA 2014:
Pipage Rounding, Pessimistic Estimators and Matrix Concentration
Nicholas J. A. Harvey, Neil Olver
http://arxiv.org/abs/1307.2274
The paper establishes concentration bounds for sums of matrices
using concavity of pessimistic estimators - this technique goes beyond
what can be achieved by negative correlation that we saw in the last class.
Using this, they get a spectral analog of the thin trees result we saw last time
and an algorithmic analog of the Marcus, Spielman, Srivastava result with
an O(log n/log log n) loss.
In preparation for this, Ankit will first introduce the "pipage rounding" technique,
following these notes by Nick Harvey:
http://www.cs.ubc.ca/~nickhar/W13/Scribe/Lecture11Scribe.pdf
http://www.cs.ubc.ca/~nickhar/W13/Scribe/Lecture12Scribe.pdf
Readings
(tentative list, subject to change)
- Twice-Ramanujan Sparsifiers
Joshua Batson, Daniel A. Spielman, Nikhil Srivastava
http://arxiv.org/abs/0808.0163
-
Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
Adam Marcus, Dan Spielman, Nikhil Srivastava
http://arxiv.org/abs/1304.4132
-
Interlacing Families II: Mixed Characteristic Polynomials and the Kadison-Singer Problem
Adam Marcus, Dan Spielman, Nikhil Srivastava
http://arxiv.org/abs/1306.3969
-
Pipage Rounding, Pessimistic Estimators and Matrix Concentration
Nicholas J. A. Harvey, Neil Olver
http://arxiv.org/abs/1307.2274
-
A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time
Jonathan A. Kelner, Lorenzo Orecchia, Aaron Sidford, Zeyuan Allen Zhu
http://arxiv.org/abs/1301.6628
-
Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs
Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng
http://arxiv.org/abs/1010.2921
-
An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
Jonathan A. Kelner, Lorenzo Orecchia, Yin Tat Lee, Aaron Sidford
http://arxiv.org/abs/1304.2338
-
Nearly Maximum Flows in Nearly Linear Time
Jonah Sherman
http://arxiv.org/abs/1304.2077
-
Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back
Aleksander Madry
http://arxiv.org/abs/1307.2205
-
Approximate Constraint Satisfaction Requires Large LP Relaxations
Siu On Chan, James R. Lee, Prasad Raghavendra, David Steurer
http://arxiv.org/abs/1309.0563
-
Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique
Raghu Meka, Avi Wigderson
http://arxiv.org/abs/1307.7615
-
Improved Cheeger's Inequality: Analysis of Spectral Partitioning Algorithms through Higher Order Spectral Gap
Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, Luca Trevisan
http://arxiv.org/abs/1301.5584
-
New Algorithms for Learning Incoherent and Overcomplete Dictionaries
Sanjeev Arora, Rong Ge, Ankur Moitra
http://arxiv.org/abs/1308.6273