Combinatorial optimization and geometry

Ms. P. Huhn
Packing problems

The knapsack problem, in which one wants to pack objects with weights and utilities while maintaining a maximum weight and maximizing the total utility, is an intuitively understandable optimization problem. It belongs to a class of packing problems that have a variety of applications in practice but, despite their simple formulation, are theoretically difficult to solve combinatorial optimization problems. We will present simple heuristics and complex exact solution methods as well as related practical problems and thus provide an insight into combinatorial optimization.

Mr. W. Klotz
Marriage, but who?

The marriage problem involves n men and n women who only partially know each other. The task is to form n couples from partners who know each other. For this to work, k men must know at least k of the women facing them. The marriage theorem (Philip Hall, 1935) states that this obvious condition is not only necessary but also sufficient for solving the problem. The marriage problem (matching problem) has many variants, applications and algorithmic solutions. We report on these.

Mr. T. Sander
Squaring the square

In 1903, Max Dehn showed that a rectangle and squares (especially of different sizes) that parcel the rectangle have commensurable sides. In 1925 the explicit parquetization of a rectangle with pairs of different squares was achieved for the first time and around 1940 the first corresponding examples for a square were created. The lecture will shed light on the problem and solution methods, whereby the use of computers, but also networks of electric currents and Kirchhoff's law play a role.

Program