AFLB
From ResearchWiki
(→Contact) |
|||
| Line 42: | Line 42: | ||
'''John''': [http://www.siam.org/proceedings/soda/2010/SODA10_065_ericksonj.pdf Maximum Flows and Parametric Shortest Paths in Planar Graphs] ''Jeff Erickson'' | '''John''': [http://www.siam.org/proceedings/soda/2010/SODA10_065_ericksonj.pdf Maximum Flows and Parametric Shortest Paths in Planar Graphs] ''Jeff Erickson'' | ||
| + | |||
| + | Abstract: | ||
| + | ''We observe that the classical maximum flow problem in any directed planar graph G can be reformulated as a parametric shortest path problem in the oriented dual graph G�. This reformulation immediately suggests an algorithm to compute maximum flows, which runs in O(n log n) time. As we continuously increase the parameter, each change in the shortest path tree can be effected in O(log n) time using standard dynamic tree data structures, and the special structure of the parametrization implies that each directed edge enters the evolving shortest path tree at most once. The resulting maximum-flow algorithm is identical to the recent algorithm of Borradaile and Klein [J. ACM 2009], but our new formulation allows a simpler presentation and analysis. On the other hand, we demonstrate that for a similarly structured parametric shortest path problem on the torus, the shortest path tree can change (n2) times in the worst case, suggesting that a different method may be required to efficiently compute maximum flows in higher-genus graphs.'' | ||
This is a paper from SODA '10 that I thought was particularly interesting. It takes an older result and casts it in a topological setting. | This is a paper from SODA '10 that I thought was particularly interesting. It takes an older result and casts it in a topological setting. | ||
Revision as of 21:32, 3 February 2010
The Algorithms For Lunch Bunch
Thursdays at 12:30.
Contents |
Spring 2010
Jan 8, 2010
- Abstracts of papers accepted to ICS2010. Full versions of the papers is here.
- Suresh: Computational Complexity and Information Asymmetry in Financial Products. Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge
- Parasaran: Playing Games without Observing Payoffs (Adam Tauman Kalai, Michal Feldman, and Moshe Tennenholtz)
- Jeff: Local Algorithms for Finding Interesting Individuals in Large Networks (Mickey Brautbar and Michael Kearns)
- John: Pan-Private Streaming Algorithms (Cynthia Dwork Moni Naor Toni Pitassi Guy Rothblum Sergey Yekhanin)
Jan14, 2010
Jeff: Combinatorial view of Markov chain Monte Carlo.
Jan 21, 2010
SODA recaps Part I: Parasaran and Jeff
Parasaran
- Finding the Jaccard Median Flavio Chierichetti. Ravi Kumar. Sandeep Pandey. Sergei Vassilvitskii
- A Model of Computation for MapReduce Howard Karloff. Siddharth Suri. Sergei Vassilvitskii
Jeff
- Universal eps-Approximators for Integrals Michael Langberg and Leonard J. Shulman
- Deletion without Rebalancing in Balanced Binary Trees Siddhartha Sen and Robert E. Tarjan
- Self-improving Algorithms for Convex Hulls Kenneth L. Clarkson and Wolfgang Mulzer and C. Seshadrhi
Jan 28, 2010
SODA recaps Part II
Suresh (Poincare inequalities):
- Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities. Alexandr Andoni, T. S. Jayram, and Mihai Pătraşcu
- Towards a Calculus for Non-Linear Spectral Gaps. Manor Mendel and Assaf Naor
John:
- Convergence, Stability, and Discrete Approximation of Laplace Spectra Tamal K. Dey, Pawas Ranjan, and Yusu Wang
- Applications of Forbidden 0-1 Matrices to Search Tree and Path Compression-Based Data Structures Seth Pettie
Feb 4, 2010
John: Maximum Flows and Parametric Shortest Paths in Planar Graphs Jeff Erickson
Abstract: We observe that the classical maximum flow problem in any directed planar graph G can be reformulated as a parametric shortest path problem in the oriented dual graph G�. This reformulation immediately suggests an algorithm to compute maximum flows, which runs in O(n log n) time. As we continuously increase the parameter, each change in the shortest path tree can be effected in O(log n) time using standard dynamic tree data structures, and the special structure of the parametrization implies that each directed edge enters the evolving shortest path tree at most once. The resulting maximum-flow algorithm is identical to the recent algorithm of Borradaile and Klein [J. ACM 2009], but our new formulation allows a simpler presentation and analysis. On the other hand, we demonstrate that for a similarly structured parametric shortest path problem on the torus, the shortest path tree can change (n2) times in the worst case, suggesting that a different method may be required to efficiently compute maximum flows in higher-genus graphs.
This is a paper from SODA '10 that I thought was particularly interesting. It takes an older result and casts it in a topological setting.
Feb 11, 2010
Arvind: Generalized MDS.
Fall 2009
Oct 30, 2009
All: Discussion of topics for Spring 2010 Algorithms Seminar on Graph Algorithms
- planarity testing
- advanced MSTs ? randomized MST
- other randomized graph algorithms
- treewidth/pathwidth
- minors
- robertson seymour (in brief)
- Baker decomposition for planar graphs
- Klein-Borradaile results on new decompositions
- shortest paths, matrix mult, new developments
- evasiveness in graph properties, and the topological angle
- Spectral graph theory?
Nov 7, 2009
- John, Raj: Practice talks for FWCG 09
- Parasaran: Geometry of Soft Clusterings
Nov 14, 2009
No AFLB (FWCG 2009)
Nov 21, 2009
Review of FWCG papers:
- Wei Zeng, Rik Sarkar, Feng Luo, Xianfeng Gu, and Jie Gao. Resilient Routing for Sensor Networks Using Hyperbolic Embedding of Universal Covering Space
- Gary L. Miller, Todd Phillips, and Donald R. Sheehy. Approximating Voronoi Diagrams with Voronoi Diagrams
(2 page abstracts here)
Dec 4, 2009
- Graph isomorphism and volumes of convex bodies. Shmuel Friedland. Presented by Christopher Earl
Papers for discussion
- Natural Algorithms (this one might be easier to read) (Chazelle, SODA 09 Best paper)
- A constructive proof of the general Lovasz Local Lemma (Moser, earlier version STOC 09 Best Student Paper)
- Affiliation Networks (Lattanzi, Sivakumar, STOC 09)
- Quantum Proofs for Classical Theorems (Drucker, Wolf)
- Unique games survey (Harb)
- Sorting and Selection with Imprecise Comparisons (Ajtai, Feldman, Hassidim, Nelson, ICALP 09)
- Homology Flows, Cohomology Cuts (Chambers, Erickson and Nayyeri, STOC 09)
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0-1 Programming. Monique Laurent. Mathematics of Operations Research, Vol. 28, No. 3 (May, 2003), pp. 470-496
Contact
If you are interested in giving a talk at AFLB or have questions, please feel free to send a mail to moeller@cs.utah.edu, praman@cs.utah.edu or avishek@cs.utah.edu. If you are planning to give a talk, we would really appreciate if you have an abstract ready a week before the talk is scheduled.
