Optimal Containment

Team

Project team leader: Dr. René Brandenberg
Ph.D. students: Dr. Stefan König (finished 2013), Dr. Lucia Roth (finished in 2010)
Prizes: Walther-von-Dyck-prize, December 2006
Prior Funding: Dr.-Ing. Leonhard Lorenz Stiftung, May 2005 - April 2006


Summary

A 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.

Prize

In 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.

k-center

Papers

Printed scientific publications

Preprints


Related student theses and projects

Supervised Dissertations

Completed Theses and Projects

Completed Master's Theses / Diploma Theses

  • Saskia Schiele - Polyhedral investigation of the k-center Problem (2015)
  • Konstantin Weddige - k-center problems on urban street networks - geometrical and graph theoretical approaches (2015)
  • Tanja Niels - Optimal Allocation of Charging Stations based on Free-floating Carsharing Data (2015)
  • Valentin Göbel - Core Sets in Optimal Containment Problems and the Szökefalvi-Nagy Problem (2013)
  • 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 Bachelor's Theses

  • Lorenz Huber - Containment for spectrahedra (2014)
  • Christoph Faltermeier - Warmstart für 1-center Routinen (2012)

Completed Projects / Interdisciplinary Projects

  • Thiemo Taube - Enhancement of a Web App for the k-Center Problem: Intersection Container and Branch-and-Bound Tree (2016)
  • Benedikt Zönnchen - Presentation of the k-Center Problem in a Web Application (2015)
  • Ismail Demir - Entwicklung eines Java-Applets zur multimedialen Lehrunterstützung - Das k-center Problem (2010)
  • 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)
  • 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

  • k-Center applet: Find your own solution to a k-center problem of your choice and compare it to an optimal solution.