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 |

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