TUM – TUM – Menü

 

 
Computational Convexity - Optimal Containment (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

News

  • (2012-07-08) Problem sheet 10 updated (correction of the definition of inner radii)
  • (2012-06-30) Please contact me soon, if you want to fix a date for the oral exam.
  • (2012-06-18) Problem sheet 7 updated (correction of relevant typing errors in 7.1 and 7.4)
  • (2012-05-24) Problem sheet 5 updated (5.1 (c) added)
  • (2012-05-19) Next week there will be an exercise class on tuesday (May, 22nd) and a normal lecture on thursday (May, 24th)
  • (2012-05-10) Problem sheet 3 corrected!
  • (2012-05-07) Please notice that we have changed the starting times of the lectures again.
  • (2012-05-03) Next thursday, 10th of may is again a normal lecture. The excercise class will take place at monday, 14th.
  • (2012-04-18) This week there will be a normal lecture instead of an exercise class at thursday 8.30. In the two weeks after pentecost I'm not at TU, so that I would miss an excercise class and two lectures. One of the lectures is replaced by the lecture this thursday. The others (exercise and lecture) will most probably be taught by Stefan König. Details will be given later (here and within the lectures)

Dates of lectures/exercise classes and office hours

type day time room starting date closing date teacher
lecture monday 12:30 a.m. to 2:00 p.m. 02.08.011 april 16th july 16th René Brandenberg
lecture tuesday 12:15 a.m. to 1:45 p.m. 02.08.011 april 17th july 17th René Brandenberg
excercise thursday 8:30 a.m. to 10:00 a.m. 02.08.011 april 19th july 19th René Brandenberg

Lecture Notes

Datum Datei Themen
2012-04-16 pdf slides of the introductory talk
2012-04-17 pdf lecture1: basics from convex analysis/geometry, part 1
2012-04-17 pdf lecture2: basics from convex analysis/geometry, part 2
2012-04-23 pdf lecture3: complexity theory: basics
2012-04-24 pdf lecture4: complexity theory: NP-hardness
2012-04-30 pdf lecture5: complexity theory: some reductions
2012-05-07 pdf lecture6: complexity theory: optimization problems
2012-05-08 pdf lecture7: norm maximization
2012-05-10 pdf lecture8: mcp-hom, foundations, part 1
2012-05-15 pdf lecture9: mcp-hom, foundations, part 2
2012-05-21 pdf lecture10: mcp-hom, exact algorithms
2012-05-24 pdf lecture11: mcp-hom, euclidean algorithms
2012-05-28 pdf lecture12: core sets for euclidean containers
2012-06-11 pdf lecture13: core set bounds for general (symmetrric) containers
2012-06-12 pdf lecture14: helly dimension and a cutting plane approach
2012-06-18 pdf lecture15: k-containment, definitions and hardness results
2012-06-19 pdf lecture16: k-containment, diameter partitioning
2012-06-25 pdf lecture17: k-containment, branch-and-bound algorithm
2012-06-26 pdf lecture18: diameter+width, definitions and lemmas
2012-07-02 pdf lecture19: diameter+width, more lemmas
2012-07-03 pdf lecture20: diameter+width, algorithms
2012-07-09 pdf lecture21: diameter+width, complexity
2012-07-10 pdf lecture22: successive radii, definitions
2012-07-16 pdf lecture23: successive radii, complexity and approximation
2012-07-17 pdf lecture24: mcp-lin and mcp-aff

Exercises

Problem Sheet Exercise Class Solutions
Sheet 1 2012-04-26 Sheet 1
Sheet 2 2012-05-03 Sheet 2
Sheet 3 2012-05-14 Sheet 3
Sheet 4 2012-05-22 Sheet 4
Sheet 5 2012-06-04 Sheet 5
Sheet 6 2012-06-14 Sheet 6
Sheet 7 2012-06-21 Sheet 7
Sheet 8 2012-06-28 Sheet 8
Sheet 9 2012-07-05 Sheet 9
Sheet 10 2012-07-12 Sheet 10

In order to test your implementation for Problem 9.1, 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.

Literature

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

  • Gritzmann. Vieweg Studium, Nr.90, Optimierung (german, not yet available)

On Convex Analysis and Convex Geometry

  • 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

  • Brieden. Geometric optimization problems likely not contained in APX. Discrete Comput. Geom., 28:201-209, 2002.
  • Brieden, Gritzmann, Kannan, Klee, Lovasz, Simonovits. Deterministic and randomized polynomial-time approximation of radii. Mathematika, 48:63-105, 2001.
  • 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, König. No Dimension Independent Core-Sets for Containment under Homothetics. arXiv:1010.4229v1.
  • 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 fi nite-dimensional normed spaces. Discrete Comput. Geom., 7:255-280, 1992.
  • 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ünbaum. Measures of symmetry for convex sets. Proc. Symp. Pure Math., 1 (Convexity), p. 271-284, 1963.
  • 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.


What is Computational Convexity?

Also sometimes seen as some part of Computational Geometry, the main ideas and techniques of Computational Convexity have their origin in fields like Linear Programming, Polyhedral Combinatorics, and Algorithmic Theory of Convex Bodies, all subsummable backwardly under the notion of Computational Convexity.

Two focuses describe the main difference betweeen Computational Convexity and typical Computational Geometry: First, instead of the typical euclidean geometry often general normed spaces are considered, and secondly, the dimension is part of the algorithmic input, as, e.g., typical in Linear Programming.

What is Optimal Containment?

In a basic Optimal Containment problem we want to compute (or approximate) extremal representatives within a given family of convex bodies , contained in or containing a fixed set. For example, given a set of points one wants to find the smallest %$n$%-dimensional cube containing it, where smallest means the scaling factor (the dilatation) and the considered family is the orbit of the standard unit cube under homothetics (dilatation and translation) or similarities (allowing also rotations).

A special case of Optimal Containment are radii of convex sets. The computation of the four basic radii (inner- and outer radius, width and diameter) is a classical problem in convex geometry. Generalizing and unifying these, several series of succesive inner and outer radii of convex bodies maybe considered. E.g. the radius of a largest %$j$%-dimensional ball contained in a given set connects diameter (1-dimensional ball) and inradius (d-dimensional) ball.

demo10.png
An optimal embedding for maximizing the radius of a disc (a 2-dimensional ball) in a 3-dimensional cube, an inner 2-radius of that cube.

Who is adressed by this lecture?

This lecture is mainly adressed to students within the masters in mathematics and mathematics of operations research. However, all other studentents having a good knowledge in Convex Analysis / Convex Geometry and Linear Optimization are welcome, too. A basic knowledge in complexity and discrete optimization may be of some value but not neccesary.

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.