TUM – TUM – Menü

 

 
Computational Convexity (MA5206)

lecture

 

lecturer: Rene Brandenberg %SBBANNER%
learning assistant and organization: Rene Brandenberg %SBBANNER%

News Dates of lectures/exercise classes and office hours Lecture notes Tutorials Exercise sheets Literature FAQ

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

  • 27th of jan: Please make an appointment for your oral exam!
  • 20th of jan: There is a nice video about bodies of constant width: Bodies of constant width 
  • 17th of jan: The claim in Exercise 10.1 (d) was correct, but the proof is a bit harder than intended. I added a hint.
  • 13th of jan: Grades of the first exam period are due until 9th of march.
  • 11th of dec: Due to your choice, there will be no lecture on 23rd of dec. Therefore we will extend the remaining wednesday lectures of the semester for 10 to 15 minutes.
  • 20th of oct: There is a nice tool for creating 3D zonotopes yourself: Zonotopebuilder 
  • 9th of oct: Lectures start on 14th of October

Dates of lectures/exercise classes and office hours

type day time room starting date closing date teacher
Lecture Monday 12.15 - 13.45 02.04.011 Oct, 14th Feb, 3rd Brandenberg
Lecture Wednesday 12.00 - 13.30 02.06.020 Oct, 16th Feb, 5th Brandenberg
Exercise Class Friday 8.30 - 10.00 02.04.011 Oct, 18th Feb, 7th Brandenberg

Lecture Notes

Lecture Notes - complete

Excercises

Problem Sheet Excercise Class Solution Outlines
Sheet 1 2013-10-18 Solution Outlines 1
Sheet 2 2013-10-25 Solution Outlines 2
Sheet 3 2013-11-08 Solution Outlines 3
Sheet 4 2013-11-15 Solution Outlines 4
Sheet 5 2013-11-22 Solution Outlines 5
Sheet 6 2013-11-29 Solution Outlines 6
Sheet 7 2013-12-06 Solution Outlines 7
Sheet 8 2013-12-13 Solution Outlines 8
Sheet 9 2013-12-20 Solution Outlines 9
Sheet 10 2014-01-17 Solution Outlines 10
Sheet 11 2014-01-24 Solution Outlines 11
Sheet 12 2014-01-31 Solution Outlines 12
Sheet 13 2014-02-05 Solution Outlines 13

Solution Outlines for all Sheets in one File

In order to test your implementation for Problem 9.3, you can download this collection of test data. For higher dimensional test-data let Mathlab create random samples in the lines described in the lectures.

Oral exames

Please make an appointment as soon as possible!

Literature

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

  • [Gri13] Gritzmann. Grundlagen der mathematischen Optimierung (in german)

On Convex Analysis and Convex Geometry

  • [BMS97] Boltyanski, Martini, Soltan. Springer Universitext, 1997.
  • [Roc97] 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

  • [BK13] Brandenberg, König. No Dimension Independent Core-Sets for Containment under Homothetics. Discrete Comput. Geom. 49, No. 1, 3-21 (2013)
  • [BK] Brandenberg, König. Sharpening Geometric Inequalities using Computable Symmetry Measures. arXiv:1310.4368
  • [Gär99] 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.
  • [GHK91] Gritzmann, Habsieger, Klee. Good and bad radii of convex polygons. SIAM J.Comput., 20(2):395-403, 1991.
  • [GK92] Gritzmann, Klee. Inner and outer j-radii of convex bodies in fi nite-dimensional normed spaces. Discrete Comput. Geom., 7:255-280, 1992.
  • [GK93] Gritzmann, Klee. Computational complexity of inner and outer j-radii of polytopes in fi nite-dimensional normed spaces. Math. Program., 59:163-213, 1993.
  • [Grü63] Grünbaum. Measures of symmetry for convex sets. Proc. Symp. Pure Math., 1 (Convexity), p. 271-284, 1963.
  • [Kle53] Klee. The critical set of a convex body. Amer. J. Pure Math., 75, 178-188, 1953.
  • [SW92] 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.