TUM – TUM – Menü

Computational Convexity
Vorlesung

Content (from the module handbook)

  • Computational Convexity is a special branch of algorithmic geometry with a focus on convex problems in arbitrary dimension (part of the input) and (if helpful) general normed spaces. Many ideas and techniques arise directly from Convex Analysis and Linear Programming.

  • In Optimal Containment one wants to find an optimal cover of a given (finite) set by an optimal convex set (a container) chosen from a family of such sets, often generated by certain allowed transformations (like dilatation, translation, rotation, or affinities) of a representative (e.g. a unit ball of a normed space). Also coverings with several containers will be touched.

News

  • 25th of oct: If "P=NP ?" belongs to the Millenium Prize Problems .
  • 17th of oct: There is a nice tool for creating 3D zonotopes yourself: Zonotopebuilder 
  • 9th of aug: Welcome on the course webpage, more infos are following soon.

Dates of lectures/exercise classes and office hours

type day time room starting date closing date teacher
Lecture Thursay 10.15 - 11.45 03.06.011 Oct, 18th Feb, 7th Brandenberg
Lecture Friday 10.15 - 11.45 03.06.011 Oct, 19th Feb, 8th Brandenberg
Exercise Class Friday 8.30 - 10.00 03.06.011 Oct, 26th Feb, 8th Brandenberg

Lecture Notes

  • Lecture Notes of the present course will always be uploaded shortly after the according lectures will have been held.
  • Since the lecture on Convex Optimization is a prerequisite for this course here are some lecture notes:

Lecture notes on Convex Optimization (MA2504), summer term 2018.

  • Below: complete chapters of the lecture-notes:

Excercises

Problem Sheet Excercise Class Solution Outlines
Sheet 1 2018-10-26 Sheet 1
Sheet 2 2018-11-02 Sheet 2
Sheet 3 2018-11-09 Sheet 3
Sheet 4 2018-11-16 Sheet 4
Sheet 5 2018-11-23 Sheet 5
Sheet 6 2018-11-30 Sheet 6
Sheet 7 2018-12-07 Sheet 7
Sheet 8 2018-12-14 Sheet 8
Sheet 9 2018-12-21  

Oral exams

Literature

In General (Convex Analysis, Optimization, and Complexity Theory)

  • Gritzmann. Grundlagen der mathematischen Optimierung (in german)

On Convex Analysis and Convex Geometry

  • Boltyanski, Martini, Soltan. Excursions into Combinatorial Geometry. Springer Universitext, 1997.
  • Rockafellar. Convex Analysis. Princeton University Press, 1996.
  • Schneider. Convex Bodies: The Brunn-Minkowski Theory, 2008.
  • Ziegler. Lectures on Polytopes, 2008.

On Complexity Theory

  • Garey, Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness,1979.
  • Papadimitriou. Computational Complexity, 1994.
  • Wegner. Complexity Theory: Exploring the Limits of Efficient Algorithms, 2005.

Special Papers On Norm Maximization

  • [Bri02] Brieden. Geometric optimization problems likely not contained in APX. Discrete Comput. Geom., 28:201-209, 2002.
  • [BGK+01] Brieden, Gritzmann, Kannan, Klee, Lovasz, Simonovits. Deterministic and randomized polynomial-time approximation of radii. Mathematika, 48:63-105, 2001.
  • [BGK00] Brieden, Gritzmann, Klee. Inapproximability of some geometric and quadratic optimization problems. In P.M. Pardalos, editor, Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, p. 96-115. Kluwer, 2000.

Special Papers On Radii And Containment

  • Brandenberg, Gonzalez Merino - The asymmetry of complete and constant width bodies in general normed spaces and the Jung constant , Israel J. Math. 218, No. 1, 489-510 (2017).
  • Brandenberg, König. No Dimension Independent Core-Sets for Containment under Homothetics. Discrete Comput. Geom. 49, No. 1, 3-21 (2013).
  • Brandenberg, König. Sharpening Geometric Inequalities using Computable Symmetry Measures. Mathematika 61, 559-580 (2015).
  • Brandenberg, Roth - New algorithms for k-center and extensions , J. Comb. Optim. 18, 376-392 (2009)
  • Gärtner. Fast and robust smallest enclosing balls. In Proc. 7th Annu. European Sympos. Algorithms, volume 1643 of Lecture Notes in Comput. Sci., p. 325-338. Springer-Verlag, 1999.
  • Gritzmann, Habsieger, Klee. Good and bad radii of convex polygons. SIAM J.Comput., 20(2):395-403, 1991.
  • Gritzmann, Klee. Inner and outer j-radii of convex bodies in finite-dimensional normed spaces. Discrete Comput. Geom., 7:255-280, 1992.
  • Gritzmann, Klee. Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces. Math. Program., 59:163-213, 1993.
  • Grünbaum. Measures of symmetry for convex sets. Proc. Symp. Pure Math., 1 (Convexity), p. 271-284, 1963.
  • Klee. The critical set of a convex body. Amer. J. Pure Math., 75, 178-188, 1953.
  • Sharir, Welzl. A combinatorial bound for linear programming and related problems. In A. Finkel and M. Jantzen, editors, STACS 92, volume 577 of Lecture Notes in Comput. Sci., p. 567-579. Springer Berlin / Heidelberg, 1992.


Research Unit M9


Department of Mathematics
Boltzmannstraße 3
85748 Garching b. München
Germany
phone:+49 89 289-16858
fax:+49 089 289-16859
sekretariat-m9ma.tum.de

Professors

Prof. Dr. Peter Gritzmann
Applied Geometry and Discrete Mathematics

Prof. Dr. Andreas S. Schulz
Mathematics of Operations Research
(affiliated member of M9)

Prof. Dr. Stefan Weltge
Discrete Mathematics

News

April 2018
Case Studies 2018: Save the date: Case Studies poster presentation on May 25th, 2018, final workshop on July 7th, 2018.