CSE642 Algorithms Seminar

Locations and Hours:

Friday 11:00-12:45 @ 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.
  • 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. Please email me (Jie Gao) if you want to be added to the list.

Schedules for Spring07: (past offering: Spring 2006, Fall 2006)

1/26, 2/2: Open problem sessions.

2/9: Joe Mitchell gives a talk on “Approximation Algorithms for the Traveling Salesman Problem with Neighborhoods”

The Euclidean TSP with neighborhoods (TSPN) problem seeks a shortest tour that visits a given collection of $n$ regions ({\em neighborhoods}).  We present the first polynomial-time approximation scheme for TSPN for a set of regions given by arbitrary disjoint fat regions in the plane.  This improves substantially upon the known approximation algorithms, and is the first PTAS for TSPN on regions of non-comparable sizes.  Our result is based on a novel extension of the $m$-guillotine method.  The result applies to regions that are ``fat'' in a very weak sense: each region $P_i$ contains a disk of radius $\Omega(diam(P_i))$, but is otherwise arbitrary.

The PTAS uses a refined version of the m-guillotine method that gives a PTAS for Euclidean TSP. I will review and describe that technique. I will emphasize several open problems that remain on this subject.

2/16: Open problem session: TSP tour with only right turns with a minimum number of turns.

2/23: Paper presentation by Supriya Garg on Voronoi game: The One-Round Voronoi Game, SoCG'02.

3/2: Graduate Research Day

3/9: Talk by Piyush Kumar (Florida State University and Stony Brook alumni).

Title: Projective Clustering and its Application to Surface Reconstruction

Abstract: Unorganized point clouds have recently become common due to their ease of acquisition through Laser, LIDAR and stereo based scanners. Applications of unorganized point cloud methods range from Bio-informatics to defense applications. In this talk, I will present our method to estimate accurate normals from unorganized point clouds in three dimensions. The main technique behind this computation is projective clustering that helps estimate better normals for point clouds sampled on sharp features. Our algorithm is parallel, external memory friendly, higher in accuracy and speed compared to previous systems and can handle sharp features and corners. I will also present the design of a parallel dynamic nearest neighbor data structure for this application.

3/16: Michael Bender gave a talk on asynchronous scheduling.

3/23: Talk by Jon Lenchner from IBM T. J. Watson Lab.

Title: Counting Ordinary Points in Line or Pseudoline Arrangements

Abstract: A classical Theorem of Csima and Sawyer from 1993 states that aside from a single arrangement of 7 lines with 3 ordinary points, any projective arrangement of n lines (or pseudolines) must contain at least 6n/13 ordinary points. An ordinary point is a point of intersection of precisely 2 lines (pseudolines). In 1951 Dirac and Motzkin conjectured that for n = 7 there must be at least n/2 ordinary points. However in 1968 McKee found an example of 13 lines with 6 ordinary points. The McKee arrangement and a 7 line arrangement with 3 ordinary points, often called the Kelly-Moser arrangement, are the only known examples of n lines with fewer than n/2 ordinary points. The question many people have pursued is whether, with the exception of these two arrangements, there must be at least n/2 ordinary points. I report on my work on this problem.

3/30: We have 2 algorithm talks today.

1st talk at 11:00am at 1211: Jeremy T. Fineman from MIT

Title: Contention Resolution with Heterogeneous Job Sizes

Randomized backoff is a common mechanism for reducing contention on a shared resource or channel.  Processes/jobs make competing attempts to access the resource, but only one can gain control of the resource at a time.  If an access attempt fails due to contention, then that process waits for a random amount of time before trying again.  On subsequent failed attempts, the waiting time increases, thereby reducing the probability of a collision.

This talk considers the contention-resolution problem for jobs with differing sizes on a "simple channel" in the setting where all jobs arrive at the same time.  I give a new backoff protocol specifically designed for jobs with multiple sizes that achieves a makespan of O(V (log log V)^3), where V is the total work of all contending jobs.  In contrast, a variant of exponential backoff only achieves a makespan of O(V log V), and binary exponential backoff has a significantly longer makespan in the worst case.

2nd talk: 2pm at 2311: Bhaskar Krishnamachari from USC

Title: Scalable Data Collection in Wireless Sensor Networks

Abstract: It is challenging to design wireless sensor networks that can operate at large scale despite severe constraints on resources such as energy, storage, and bandwidth. We show how mathematical modeling and optimization can provide rich insights into fundamental limitations and the design of efficient wireless sensor networks protocols through three case studies. In the first, we use a constrained-optimization framework to identify fundamental scaling laws for data-centric storage and querying, quantifying the application-specific conditions under which arbitrarily large networks may be deployed. In the second case study, we use renewal theory and derive an interesting optimality criterion to design a receiver-feedback enhancement of the IEEE 802.15.4 MAC protocol that ensures good throughput and energy performance even in highly dense settings. Finally, we show how Lagrange duality can be used to derive a market-based solution for the problem of fair and efficient rate allocation in tree-based data gathering.

4/6: No meeting, spring break.

4/13: Paper presentation by Marc Tchiboukdjian

Abstract: This paper shows how to generate a cache-oblivious memory layout of a well-shaped finite-element mesh G. This cache-oblivious mesh layout enables asymptotically optimal  mesh updates, in which each vertex communicates with all of its neighbors. Mesh updates is the building block of iterative linear system solver. For block size B and cache size M, the mesh update cost is O(1+|G|/B), assuming the tall cache assumption M = O(B^d ), where d is the dimensionality of the mesh’s geometric domain. The layout algorithm runs cache-obliviously in O(|G|log^2 |G|) operations and O(1+|G|log^2 |G|/B) memory transfers with high probability. We give a faster layout algorithm which runs cache-obliviously in O(|G|log|G|loglog|G|) operations and O(1+|G|log|G|loglog|G|) memory transfers with high probability such that with M = O(B^d ), mesh update cost is O(1+|G|/B). The approach combines ideas from VLSI theory, graph separators, and I/O-efficient computing, and presents simplified and improved methods for building fully-balanced decomposition trees from the VLSI literature and k-way partitioning from the graph-separator literature.

List of papers for presentation:

  1. Geographic routing using hyperbolic space, Robert Kleinberg, to appear in INFOCOM’07.
  2. The Voronoi game:
    1.  Applet.
    2. Papers: The One-Round Voronoi Game, SoCG'02 (presented by Supriya Garg).
    3. The One-Round Voronoi Game Replayed, WAFR'03.
  3. Raghavan and Spinrad, Robust algorithms for restricted domains, SODA'01.
  4. Pseudo-triangulations:
    1. Ileana Streinu, Pseudo-Triangulations, Rigidity and Motion Planning, DCG, vol. 34, no. 4, pp. 587-635, Nov. 2005.
    2. Pseudo-triangulations – a survey, Gunter Rote, Francisco Santos and Ileana Streinu, manuscript, Dec 2006. arXiv:math.CO/0612672. Present chapter 1 (intro), 2 (basic properties), 9 (applications), and any additional materials you would like.
    3. Slides for pseudo-triangulations.
  1. Learning of manifolds in high-dimensional space.
    1. Isomap, Locally Linear Embedding (LLE).

Last updated: 2/20/07