[Colloquium] TTIC Talk: Mohammad Hossein Bateni, Princeton

[Julia MacGlashan]

When:             *Tuesday, Mar 16 @ 11:00am*

Where:           * TTIC Conference Room #526*, 6045 S Kenwood Ave, 5th Floor


Who:              * **Mohammad Hossein Bateni*, Princeton University


Title:          *      **PTAS for planar Steiner forest***



 We describe a thorough complexity study of Steiner forest in bounded
treewidth graphs, planar graphs, and bounded genus graphs.  We give the
first polynomial-time approximation scheme for the Steiner forest problem on
planar graphs and, more generally, on graphs of bounded genus.  The crux of
the process is a clustering procedure called prize-collecting clustering
that breaks down the input instance into separate subinstances which are
easier to handle.  We also give a polynomial-time approximation scheme for
Steiner forest on graphs of bounded treewidth, a problem that is NP-hard
even on graphs of treewidth 3, and show that Steiner forest can be solved in
polynomial time for series-parallel graphs (graphs of treewidth at most two)
by a combination of dynamic programming and minimum cut computations.

This is joint work with MohammadTaghi Hajiaghayi and Daniel Marx.

Web page:     http://mhbateni.com/academic/

Host:              Julia Chuzhoy, cjulia at ttic.edu
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100315/4c7050ce/attachment.htm