CSE642 Algorithm Seminar
Locations and Hours:
Wednesday 11:30 (sharp) -12:45 @
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
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
- 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
We have a mailing list.
Further announcement will be distributed through the list. Please email
(jgao at cs) to be added to the mailing
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
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
Algorithm for the Asymmetric Traveling Salesman Problem.
Apr 21: Mohammad Irfan presents Graphical
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
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.
Complexity of Computing a Nash Equilibrium, Constantinos
Daskalakis, Paul W. Goldberg, Christos Papadimitrou,
CACM. To be presented by Vijit
Games, Michael Keans. To be
presented by Mohammad Irfan.
Dimension, Shortest Paths, and Provably Efficient Algorithms, Ittai
Abraham, Amos Fiat, Andrew V. Goldberg, and Renato F. Werneck, SODA
2010. To be presented by Shang Yang.
- Testing Planarity of Partially
Embedded Graphs, Patrizio Angelini, Giuseppe Di Battista, Fabrizio
Frati, Vít Jelínek,
Jan Kratochvíl, Maurizio Patrignani, and Ignaz Rutter, SODA 2010.
- An O(log n/ log log
Algorithm for the Asymmetric Traveling Salesman Problem, Arash
Asadpour, Michel X. Goemans, Aleksander Mądry, Shayan Oveis Gharan, and
Amin Saberi, SODA 2010. This paper received the best paper award. To be presented by Roozbeh Ebrahimi.
- How Far Can You Reach? Ciprian
Borcea and Ileana Streinu, SODA 2010. To be presented by Yogesh Srihari.
- Randomized Shellsort: A
Simple Oblivious Sorting Algorithm, Michael
T. Goodrich, SODA 2010.
- A Faster
Algorithm for Betweenness Centrality,Ulrik Brandes.