AFLB

From ResearchWiki

(Difference between revisions)
Jump to: navigation, search
(→Mar 4, 2010)
(→Feb 25, 2010)
Line 60: Line 60:
=== Feb 25, 2010 ===
=== Feb 25, 2010 ===
-
 
-
'''Josh''': [http://graphics.stanford.edu/projects/lgl/papers/cghs-rnrop-10/cghs-rnrop-10.pdf Road Network Reconstruction for Organizing Paths] by ''Daniel Chen, Leo Guibas, John Hershberger, and Jian Sun''
 
-
 
-
Abstract:
 
-
''We consider the problem of reconstructing a road network from a collection of path traces and provide guarantees to the accuracy of the reconstruction under reasonable assumptions. Our algorithm can be used to process a collection of polygonal paths in the plane so that shared structures (subpaths) among the paths in the collection can be discovered and the collection can be organized to allow efficient path similarity queries against new query paths on the same road network. This is a timely problem, as GPS or other location traces of both people and vehicles are becoming available in a large scale and there is a real need to create appropriate data structures and data bases for such data.''
 
=== Mar 4, 2010 ===
=== Mar 4, 2010 ===

Revision as of 21:48, 12 February 2010

The Algorithms For Lunch Bunch

Thursdays at 12:30.

Contents

Spring 2010

Jan 8, 2010

Jan14, 2010

Jeff: Combinatorial view of Markov chain Monte Carlo.

Jan 21, 2010

SODA recaps Part I: Parasaran and Jeff

Parasaran

Jeff

Jan 28, 2010

SODA recaps Part II

Suresh (Poincare inequalities):

John:

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: A Unified Algorithmic Framework for Multi-Dimensional Scaling

Abstract: In this paper, we propose a unified algorithmic framework for solving many known variants of MDS. Our algorithm is a simple iterative scheme with guaranteed convergence, and is modular; by changing the internals of a single subroutine in the algorithm, we can switch cost functions and target spaces easily. In addition to the formal guarantees of convergence, our algorithms are fast; in most cases, they converge to better quality solutions faster than existing methods. We expect that this framework will be useful for a number of MDS variants that have not yet been studied.

This is a joint work with Jeff Philips and Suresh Venkatasubramanian.

Feb 18, 2010

Feb 25, 2010

Mar 4, 2010

Jags: [Will pick the paper]

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

Papers for discussion

Recently Seen on Arxiv

STOC 2010

Add papers here that you found interesting (and link to full version if available)

  • Efficiently Learning Mixtures of Two Gaussians. Adam Tauman Kalai (Microsoft), Ankur Moitra (MIT), and Gregory Valiant (UC Berkeley)
  • Measuring Independence of Datasets. Vladimir Braverman and Rafail Ostrovsky (UCLA)
  • On the Geometry of Differential Privacy. Moritz Hardt (Princeton University) and Kunal Talwar (Microsoft Research)
  • Recognizing well-parenthesized expressions in the streaming model Frederic Magniez (LRI, Univ. Paris-Sud, CNRS), Claire Mathieu (Brown University) and Ashwin Nayak (U. Waterloo and Perimeter Institute)
  • Weighted Geometric Set Cover via Quasi-Uniform Sampling. Kasturi Varadarajan (University of Iowa)
  • A Sparse Johnson-Lindenstrauss Transform. Anirban Dasgupta and Ravi Kumar and Tamas Sarlos (Yahoo! Research)

Other Papers

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.

Retrieved from "http://www.cs.utah.edu/~suresh/mediawiki/index.php/AFLB"
Personal tools