Spring2010 CSE642 Algorithm Seminar

Locations and Hours:

Wednesday 11:30 (sharp) -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:

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.


Jan 27      Steve proposed the following problem. Given n numbers 1, 2, ..., n, and m sets S1, S2, ..., Sm, each set Si is a subset of numbers between 1 and n. Find one number from each set such that the maximum gap is minimized. Find a polynomial algorithm or show this problem is NP-hard. Pablo scribed some notes.

Feb 3        Joondong showed that the problem from Jan 27 is NP-complete, by reduction from SETCOVER.

Feb 10      No meeting, class canceled due to snow storm.

Feb 17      Charles led the discussion on a problem from computational biology & drug design.

Feb 24      We continue to brainstorm Charles' problem to further refine it.

Mar 3        Joe had a new problem of patroling guards in a polygon.

Mar 10      We re-visit the pair separation tour problem. Steve proposed to exhuastively search for all centers and choose the closer one from each pair as the one included inside the cycle. Once this is determined, we use the PTAS for red-blue separation to solve the problem. So far we have not found any counter example for this idea. It remains open to either prove it or disprove it.

Mar 17       Steve's conjecture was disproved by Giordano's counterexample.

Mar 24       Shang Yang presents
Highway Dimension, Shortest Paths, and Provably Efficient Algorithms.

Mar 31: spring break

Apr 7:      Paper presentation by Vijit Kharbanda:
The Complexity of Computing a Nash Equilibrium
               Paper presentation by Chaitanya:
A Faster Algorithm for Betweenness Centrality.

Apr 14     Roozbeh Ebrahimi presents 
An O(log n/ log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem.

Apr 21:    
Mohammad Irfan presents Graphical Games.

Apr 28     
Yogesh Srihari presents How Far Can You Reach?

May 5      Alon Efrat will give a talk.

May 12    Sandor Fekete will give a talk. Title and abstracts are shown below.

Exact Solutions and Bounds for General Art Gallery Problems

The classical Art Gallery Problem asks for the minimum number of guards that achieve visibility coverage of a given polygon. This problem is known to be NP-hard, even for very restricted and discrete special cases.  For the case of vertex guards and simple orthogonal polygons, Cuoto et al. have recently developed an exact method that is based on a set-cover approach. For the general problem (in which both the set of possible guard positions and the point set to be guarded are uncountable), neither constant-factor approximation algorithms nor exact solution methods are known.

We present a primal-dual algorithm based on linear programming that provides lower bounds on the necessary number of guards in every step and---in case of convergence and integrality---ends with an optimal solution. We describe our implementation and give results for an assortment of polygons, including non-orthogonal polygons with holes.

This is talk is based on an expanded and enhanced version of an ALENEX 2010 paper; coauthors are Alexander Kroeller, Tobias Baumgartner, and Christiane Schmidt from Braunschweig.


Reading lists:
Past offerings: