Spring 2010 CSE642 Algorithm Seminar

Locations and Hours:

Friday 11:00 -12:30 @ Computer Science Lounge (CS Building 1211).

Course Description:

This reading group provides a meeting place for Stony Brook faculty, postdocs, and students interested in the analysis of algorithms. We meet once a week, with one of three different missions:

• Paper presentations -- This is fairly informal, with one person (i.e. student) responsible each time for leading the discussions. Nobody will have to lead for more than one paper per semester. We highly encourage students to volunteer for paper presentations, as it is a good opportunity to learn how to give a technical presentation and our reading group is a friendly group of audience to start with. The list of papers you can choose to present, if you do not have a paper already, can be found below.
• Open Problem Bull Sessions -- where we pose and attack accessible research problems. A good time is had by all.
• Road Trips -- to the special computational geometry or theory days at NYU, Columbia, and the like.

You can get one credit for participating by simply registering for CSE 642. You are also welcome to come without registering. 

We have a mailing list. Further announcement will be distributed through the list. Please subscribe here.  

Schedule:

• Feb 4th: Joe brought the puzzles on Communications of the ACM. Jie mentioned a problem on structural balance in social networks. Thanks to Roozbeh Ebrahimi Soorchaei, we have scribed notes on the problems.

• Feb 11th: presentation by visiting student Stefan Huber. The title and abstract of the talk are as follows: 

  Theoretical and Practical Results on Straight Skeletons of Planar Straight-Line Graphs
  
  The straight skeleton of a simple polygon, or more generally, of a planar straight-line graph, is a geometric structure similar to Voronoi diagrams. Straight skeletons have many applications, including the computation of straight-line oset curves, generating roofs and terrains, or solving mathematical origami problems.
  
  We start with an extension of the so-called motorcycle graph to planar straight-line graphs and present new theoretical contributions regarding the relation of the motorcycle graph and the straight skeleton of arbitrary planar straight-line graphs. We give a new characterization of the straight skeleton based on the lower envelope of partial linear functions with domains that depend on the motorcycle graph. An immediate application is a straight-skeleton algorithm based on graphics hardware by rendering the lower envelope of 3D slabs.
  
  We also present a novel wavefront-type algorithm for the computation of straight skeletons which bridges the gap between theory and practice of straight skeleton computations. Our algorithm handles arbitrary planar straight-line graphs, is easy to implement, and is fast enough to handle complex data. It can be expected to run in O(n log n) time in practice and its worst-case complexity is O(n^2 log n) for an n-vertex input graph. Experimental results conrm an average runtime of 20 n log n on a standard PC for virtually all of our 13,500 datasets. Compared to the current CGAL implementation, this constitutes an average gain in performance by a multiplicative factor of n, or at least one to two orders of magnitude for our datasets.

• Feb 18th: open problem session. We revisited the structural balance problem.

• Feb 25th: open problem session. We revisited the structural balance problem on a local search algorithm.

• March 4th: open problem session. New results on optimal solution to turn a weakly balanced graph to strongly balanced.

• March 11th: presentation by David Bergman, the CMU student (undergrad and MS from Stony Brook). His talk title and abstract are as follows: 
  
  Title: Manipulating Multivalued Decision Diagrams for Combinatorial Optimization Problems.
  
  Abstract: In this talk we study the application of limited-width multivalued decision diagrams (MDDs) as discrete relaxations for combinatorial optimization problems. We introduce a new compilation method to efficiently construct such MDDs and also present a number of algorithms for MDD manipulation that yield stronger relaxations. Our
  methodology is applied to set covering problems, and evaluated against relaxations based on linear programming. The experimental results indicate that MDD-based relaxations are particularly effective on structured problems, outperforming state-of-the-art integer programming technology by several orders of magnitude.

• March 18th: Steve Skiena led the discussion on a new problem. 

• March 25th: Presentation by Dr. Walter Diumo on elevator scheduling problem.

• April 1st: Paper presentation by Chloe Kong on Shortest Non‐Crossing Walks in the Plane, J.Erickson, A. Nayyer, SODA'11.

• April 8th: Paper presentation by Jethro Chu on A Stackelberg Strategy for Routing Flow over Time, U. Bhaskar, L.Fleischer, E. Anshelevic, SODA'11.

• April 15th: Michael Bender led the discussion on a new problem.

• April 22nd: spring break. 

• April 29th: CS department GRC day, no reading group.

• May 6th: Joe brought a game problem of grabbing pizza pieces, brownies, sub sandwiches, etc. 

• NY theory day, May 13th, Columbia, NY.

1. A Stackelberg Strategy for Routing Flow over Time, U. Bhaskar, L.Fleischer, E. Anshelevic, SODA'11.
2. Shortest Non‐Crossing Walks in the Plane, J.Erickson, A. Nayyer, SODA'11.
3. On the Complexity of Time‐Dependent Shortest Paths, L. Foschini, J. Hershberger, S. Suri, SODA'11.
4. Dimensionality Reduction: Beyond the Johnson‐Lindenstrauss Bound, Y. Bartal, B. Recht, L. Schulman, SODA'11.
5. Computing Replacement Paths in Surface Embedded Graphs, J. Erickson, A. Nayyeri, SODA'11.
6. On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs, Xin He, Huaming Zhang, SODA'11.
7. Triangulating the Square and Squaring the Triangle, Quadtrees and Delaunay Triangulations are Equivalent, Maarten Loffler, Wolfgang Mulzer, SODA'11.
   

• Spring 2010
• Fall 2008
• Spring 2008
• Fall 2007
• Spring 2007
• Fall 2006
• Spring 2006