CSE642 Algorithms Seminar
Locations and Hours:
Wednesday 11:00-12:15 @ 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 email me (jgao at cs) to be added to the mailing list.
September 3: introduction and open problem session (Joe proposed the Shrokuro problem).
September 10: Special session featuring Ashish Lohia and Shang Yang’s RPE. 10am-12am. Location: AMS Seminar Room, Math 1-122A.
September 17: Invited speaker: Prof. Matya Katz from Ben Gurion University
Title: Polynomial-Time Approximation Schemes for Piercing and Covering with Applications in Wireless Networks
Abstract: Let D be a set of disks of arbitrary radii in the plane, and let P be a set of points. In this talk we focus on the following problem (and mention several related problems), with applications in wireless networks. Assuming P contains the set of center points of disks in D, find a minimum-cardinality subset P^* of P (if exists), such that each disk in D is pierced by at least h points of P^*, where h is a given constant. We call this problem "minimum h-piercing". We present a constant-factor approximation algorithm for this problem, followed by a polynomial-time approximation scheme. The PTAS is based on an adapted and extended version of Chan's separator theorem. The talk is based on join work with Paz Carmi and Nissan Lev-Tov.
September 24: Open problem session led by Luis Ortiz on a coloring problem: given a graph and a threshold for each node between [1, degree-1], such that a node will be colored black if the number of black neighbors is strictly smaller than the threshold, and colored white otherwise. Question: is such a coloring always possible? If so, give an algorithm. If not, is testing for colorability NP-complete?
October 1: holiday, no class.
1. Fall workshop on Computational Geometry 2008: October 31-November 1st, at RPI. 2-page abstract submission Deadline is September 15th, 2008.
2. NY theory day, TBD.
3. New York Computer Science and Economics Day (NYCE Day), October 3rd.