|Mittagsseminar Talk Information|
Date and Time: Thursday, March 10, 2005, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Jan Remy
Approximation Schemes for Node-Weighted Geometric Steiner Tree Problems
In this paper, we consider the following variant of the geometric Steiner tree problem. Every point u which is not included in the tree costs a penalty of π(u) units. Furthermore, every Steiner point we use costs cS units. The goal is to minimize the total length of the tree plus the penalties. We prove that the problem admits a polynomial time approximation scheme.
Our PTAS uses a new technique which allows us to avoid the so-called Patching Lemma [Arora 98] or equivalents. It may thus open new possibilities to find approximation schemes for geometric optimization problems that include complicated topology. Furthermore the techniques we use provide a more general framework which can be applied to geometric optimization problems with more complex objective functions.
(Joint work with Angelika Steger)
Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)
Previous talks by year: 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
Information for students and suggested topics for student talks
Automatic MiSe System Software Version 1.3392 | admin login