Computational Convexity (MA5206)
|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.
- 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 NotesLecture Notes - complete
|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|
Oral examesPlease make an appointment as soon as possible!
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 finite-dimensional normed spaces. Discrete Comput. Geom., 7:255-280, 1992.
- [GK93] Gritzmann, Klee. Computational complexity of inner and outer j-radii of polytopes in finite-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.