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.
- 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 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 1
- Lecture 2
- Lecture 3
- Lecture 4
- Lecture 5
- Lecture 6
- Lecture 7
- Lecture 8
- Lecture 9
- Lecture 10
- Lecture 11
- Lecture 12
- Lecture 13
- Lecture 14
- Lecture 15
- Lecture 16
- Below: complete chapters of the lecture-notes:
- Chapter 1 - Basics from Convex Analysis
- Chapter 2 - Complexity Theory - A short introduction
- Chapter 3 - Some basic problems in Computational Convexity and Optimal Containment, and Norm Maximization
- Chapter 4 - Containment under homothety
|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|
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.