Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, December 18, 2008, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Zhen Hao (Univ. Heidelberg, Research Group Combinatorial Optimization)
To find a shortest Steiner tree S* (with length L*) which connects a given set R of mutually disjoint, connected polygons is an NP-hard problem, called the geometric SMTN problem.
We show that we can construct a "near-optimal" Steiner tree S in polynomial running time: for a given ε > 0 we construct a PTAS (polynomial-time approximation scheme) which computes a Steiner tree S, where S connects R and has length L <= (1 + ε)L*.
The algorithm is based on a subdivision method called m-guillotine method, originally developed by J.S.B. Mitchell in 1996.
Automatic MiSe System Software Version 1.4803M | admin login