Preprint
26 search hits
-
A bijection between the d-dimensional simplices with distances in {1,2} and the partitions of d+1
(2005)
-
Christian Haase
Sascha Kurz
- We give a construction for the d-dimensional simplices with all distances in {1,2} from the set of partitions of d+1.
-
A generalized job-shop problem with more than one resource demand per task
(2011)
-
Joachim Schauer
Cornelius Schwarz
- We study a generalized job-shop problem called the Laser Sharing Problem with fixed tours (LSP-T) where the tasks may need more than one resource simultaneously. This fact will be used to model possible collisions between industrial robots. For three robots we will show that the special case where only one resource is used by more than one robot is already NP-hard. This also implies that one machine scheduling with chained min delay precedence constraints is NP-hard for at least three chains. On the positive side, we present a polynomial algorithm for the two robot case and a pseudo-polynomial algorithm together with an FPTAS for an arbitrary but constant number of robots. This gives a sharp boundary of the complexity status for a constant number of robots.
-
A homotopy argument and its applications to the transformation rule for bi-Lipschitz mappings, the Brouwer fixed point theorem and the Brouwer degree
(2005)
-
Christian G. Simader
- The main purpose of the paper is to present an elementary self-contained proof of the change of variables formula for injective, locally bi-Lipschitz mappings. The proof is based on a homotopy argument. Various properties of bi-Lipschitz mappings are studied. As a by-product Lipschitz variants of the classical implicit function theorem and the local diffeomorphism theorem are proved. With the help of the homotopy argument a simple proof is given of Brouwer’s fixed point theorem and the main properties of Brouwer’s degree of mapping.
-
A note on Erdös-Diophantine graphs and Diophantine carpets
(2005)
-
Axel Kohnert
Sascha Kurz
- A Diophantine figure is a set of points on the integer grid $\mathbb{Z}^{2}$ where all mutual Euclidean distances are integers. We also speak of Diophantine graphs. The vertices are points in $\mathbb{Z}^{2}$ (the coordinates)and the edges are labeled with the distance between the two adjacent vertices, which is integral. In this language a Diophantine figure is a complete Diophantine graph. Two Diophantine graphs are equivalent if they only differ by translation or rotation of vertices. Due to a famous theorem of Erdös and Anning there are complete Diophantine graphs which are not contained in larger ones. We call them Erdös-Diophantine graphs. A special class of Diophantine graphs are Diophantine carpets. These are planar triangulations of a subset of the integer grid. We give an effective construction for Erdös-Diophantine graphs and characterize the chromatic number of Diophantine carpets.
-
A survey of the higher Stasheff-Tamari orders
(2012)
-
Jörg Rambau
Victor Reiner
- The Tamari lattice, thought as a poset on the set of triangulations of a convex polygon with n vertices, generalizes to the higher Stasheff-Tamari orders on the set of triangulations of a cyclic d-dimensional polytope having n vertices. This survey discusses what is known about these orders, and what one would like to know about them.
-
An exact column-generation approach for the lot-type design problem
(2012)
-
Sascha Kurz
Miriam Kießling
Jörg Rambau
- We consider a fashion discounter distributing its many branches with
integral multiples from a set of available lot-types. For the problem of
approximating the branch and size dependent demand using those lots
we propose a tailored exact column generation approach assisted by fast
algorithms for intrinsic subproblems, which turns out to be very efficient
on our real-world instances.
-
Bounds for the minimum oriented diameter
(2008)
-
Sascha Kurz
Martin Lätsch
- We consider the problem of finding an orientation with minimum diameter of a connected bridgeless graph. Fomin et. al. discovered a relation between the minimum oriented diameter an the size of a minimal dominating set. We improve their upper bound.
-
Convex hulls of polyominoes
(2007)
-
Sascha Kurz
- In this article we prove a conjecture of Bezdek, Brass, and Harborth concerning the maximum volume of the convex hull of any facet-to-facet connected system of $n$ unit hypercubes in $mathbb{R}^d$. For $d=2$ we enumerate the extremal polyominoes and determine the set of possible areas of the convex hull for each $n$.
-
Counting polyominoes with minimum perimeter
(2005)
-
Sascha Kurz
- Es wird die Anzahl der wesentlich verschiedenen Polyominoes der Ordnung n mit minimalem Umfang p(n) bestimmt.
-
Das Optimierungslabor – ein Erfahrungsbericht
(2012)
-
Miriam Kießling
Tobias Kreisel
Sascha Kurz
Jörg Rambau
Konrad Schade
Cornelius Schwarz
- Seit mehreren Jahren besuchen uns Schülerinnen und Schüler an der
Universität zu Anlässen wie dem Tag der Mathematik, dem Girls’ Day,
der MINT-Universität oder einfach auf Initiative ihrer
Klassenleitungen. Sie möchten einen Einblick in die Welt der
Mathematik über die Schulmathematik hinaus bekommen. Doch wie lässt
sich die Brücke vom Schulstoff zu den Inhalten der
Universitätsmathematik schlagen? Und: findet man einen
Themenschwerpunkt, bei dem ein aktives Mitmachen trotz fehlender
Vorkenntnisse in Anbetracht begrenzter Zeit möglich wird?
In der diskreten Optimierung lassen sich Problem-Modellierung und
Problem-Lösung sehr gut trennen. Selbst forschungsnahe Modelle der
ganzzahligen linearen Optimierung (MILP-Modelle) basieren auf sehr
elementaren Überlegungen, wie die Entscheidungsmöglichkeiten, Ziele
und Restriktionen eines Alltagsproblems in Variablen,
Bewertungsfunktionen, Gleichungen und Ungleichungen ausgedrückt werden
können. Wie dann optimale Lösungen gefunden werden, erfordert zwar
tiefergehende Mathematik, es gibt aber Software dafür, in der das
Wissen aus Teilen des Mathematik-Studiums und der mathematischen
Forschung kondensiert vorliegt.
Unser Vermittlungsziel: Schülerinnen und Schüler wissen nach dem
Besuch, dass man verschiedenste Probleme angreifen kann, indem man sie
in die Sprache der Mathematik übersetzt, denn in Software gegossenes
mathematisches Know-How kann dann diese Probleme lösen, ohne etwas
über die Probleme selbst zu wissen. Unsere Idee für eine Maßnahme:
Ein Optimierungslabor. Die Schülerinnen und Schüler isolieren in
Teamarbeit die wesentlichen logischen Merkmale von Sudokulösen,
Rucksackpacken, Routenplanung u.v.a.m. Dann übersetzen sie die
Problemstellungen in die Sprache der Mathematik (hier: MILP-Modelle)
und lassen sie (unterstützt durch unser Team) von Computerprogrammen
lösen (MILP-Löser), die nichts anderes als diese Sprache verstehen.
Schließlich übersetzen sie die mathematischen Lösungen wieder in die
Sprache der Problemstellung. Erfahrungen mit der Modellierung auf
Basis linearer Gleichungssysteme können dabei aus dem Schulunterricht
eingebracht werden.
In diesem Bericht wollen wir unsere Erfahrungen mit konkreten Details
der Umsetzung schildern.
