You are here: Projekte > Containment (02 Mar 2012, UnknownUser)
Team
SummaryA central point of this project is the combination of some recent results on so called core-sets with geometric inequalities and typical techniques from combinatorial optimization. We obtained new and significantly faster approximation routines for minimal containment under homothetics, one of the most basic classes of containment problems, and k-center, a variant of facility location in combinatorial optimization, which seemed to be almost intractable only a couple of years ago. Another important result of the project is the paper “No dimension independent core-sets for minimal containment under homothetics” (Preprint Version ), which we finished recently. Its main theorem shows the non-generalizability of the (fully) polynomial time approximation schemes for the minimal enclosing ball problem and Euclidean k-center using core-sets, when replacing the Euclidean ball with other (symmetric) containers.
In parts, the research on optimal containment contributed also to the project Modeling and optimization of correction measures for human extremities within the BMBF research program on “Mathematics – Key Technology for the Future, Joint Projects between Universities and Industry”. We investigated questions in computational geometry arising in semi-automated operation planning when treating congenital or post-traumatic deformities of lower extremities with fully implantable intramedullary limb lengtheners.
PrizeIn december 2006 René Brandenberg was awarded with the Walther-von-Dyck-prize of the faculty of mathematics at Technische Universität München (TUM) for his research proposal Optimal Containment - Theory, algorithms, and applications. |
 |
Papers
Printed scientific publications
- R. Brandenberg, S. König - No Dimension Independent Core-Sets for Containment under Homothetics (extended abstract), Proc. 27th ACM Symp. Comp. Geom., 464-471 (2011).
- R. Brandenberg, L. Roth - Minimal containment under homothetics. A simple cutting plane approach , Comput. Optim. Appl. 48, 325-340 (2011)
- R. Brandenberg, L. Roth - New algorithms for k-center and extensions , J. Comb. Optim. 18, 376-392 (2009)
- R. Brandenberg, L. Roth - New algorithms for k-center and extensions , Lect. Notes Comput. Sci. 5165, 64-78 (2008)
- R. Brandenberg, T. Gerken, P. Gritzmann, L. Roth - Modeling and Optimization of Correction Measures for Human Extremities , Mathematics – Key Technology for the Future, Joint Projects between Universities and Industry 2004 -2007, Jäger, Willi; Krebs, Hans-Joachim (Eds.) (2008)
Preprints
- R. Brandenberg, S. König - No Dimension Independent Core-Sets for Containment under Homothetics (full version), invited for submition for a special issue of Discrete Comput. Geom. concerning the 27th ACM Symposium on Computational Geometry (SOCG 2011), Preprint Version .
- R. Brandenberg, D. Bremner – Maximum margin simplices in polytopal or spherical containers, in preparation.
- R. Brandenberg, S. König, L. Roth - Theory, complexity, and algorithms for computing minimal enclosing cylinders and variants, in preparation.
Related student theses and projects
Supervised Dissertations
- Stefan König - Geometric Methods for tomographic reconstruction
- Lucia Roth - Optimal Containment (2010)
Ongoing Theses and Projects
- Christoph Faltermeier - Warmstart für 1-center Routinen (Bachelor's Thesis)
- Thiemo Taube - Implementierung schneller k-center Heuristiken in MATLAB (Interdisciplinary Project)
Completed Theses and Projects
Completed Diploma Theses
- Katharina Sury - k-Center with Line Segments and Piecewise Linear Regression (2012)
- Valentin Breuss - Optimale Standortwahl in Verkehrsnetzwerken - ein Vergleich von geometrischen und graphentheoretischen Ansätzen (2010)
- Stefan König - Optimales Containment, Helly-Type-Theorems und Core Sets - Ein Überblick (2009)
- Martina Laumeyer - Containment Probleme: Lagrange-Relaxation und -Dualität (2009)
- Brigitte Gölles - Algorithmen für Optimale Containment Probleme von Polytopen in Würfeln unter Ähnlichkeit (2009)
- Andreas Arnold - Approximationsalgorithmen zur Lösung von allgemeinen k-Containment Problemen (2009)
- Sandra Rauscher - On planar k-containment problems under similarity (2009)
- Kathrin Frankl - Algorithmen zur Punktmengenüberdeckung mit minimaler Containerzahl (2008)
- Tobias Braunschober - Verankerte und freie einschließende Zylinder: Branch and Bound-Algorithmen zur Bestimmung ɛ-optimaler Lösungen bei der automatisierten dreidimensionalen Operationsplanung zur Femurkorrektur (2007)
- Simon Rittsteiger - Shape Fitting Algorithmen, Theorie, Implementation und Anwendung in der chirurgischen Operationsplanung (2006)
- Lucia Roth - Exakte und ε-Approximative Algorithmen zur Umkugelberechnung (2005)
Completed Projects / Interdisciplinary Projects
- Yuzhang Zong - Dicke Simplexe in Würfeln (2009)
- Stefan König - Optimales Containment mit Ellipsoiden, elliptischen Zylindern und Kegeln (2008)
- Kathrin Frankl - Praktische Methoden zur Lösung minimaler Multi-Contaiment Probleme unter Homothetie (2007)
- Andreas Arnold , Teresa Scholz - Ein verbessertes Branch and Bound Verfahren für euklidische k-center Probleme unter Verwendung einer gemischtganzzahligen SOCP Formulierung (2007)
- Irena Hofmann - Drei Algorithmen zur approximativen Lösung des euklidischen 2-Center-Problems (2006)
- Ismail Demir - Entwicklung eines Java-Applets zur multimedialen Lehrunterstützung - Das k-center Problem (2010)
- Tobias Braunschober, Manuel Mayr - Computational Convexity - Berechnung von Dicke und Zylinderradius (2006)
- Andreas Nill, Sonja Wöhnl - Adaptive Algorithmen zur Lösung metrischer k-center Probleme (2006)
Software
- CoCon - The Computational Containment Library (A Matlab library for the solution of various optimal containment problems)
- k-Center applet: Find your own solution to a k-center problem of your choice and compare it to an optimal solution.
Topic revision: r49 - 02 Mar 2012 - 09:30:21 - UnknownUser
Projekte
Impressum | Disclaimer und Rechtshinweise | AnregungenCopyright Technische Universität München, M9