Spring 2010 CSE642 Algorithm Seminar
Locations and Hours:
Friday 11:00 -12:30 @ Computer Science Lounge (CS Building 1211).
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:
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.
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:
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
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.