## Preprint

### Refine

#### Document Type

- Preprint (27) (remove)

#### Keywords

- Kombinatorik (9)
- integral distances (6)
- erschöpfende Suche (5)
- exhaustive search (5)
- ganzzahlige Abstände (5)
- Durchmesser (4)
- ganzzahlige Punktmengen (4)
- Diskrete Geometrie (3)
- Diskrete Optimierung (3)
- Operations Research (3)

#### Institute

- Mathematik (27)
- Informatik (1)
- Wirtschaftswissenschaften (1)

- A bijection between the d-dimensional simplices with distances in {1,2} and the partitions of d+1 (2005)
- 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)
- 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)
- 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)
- 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)
- 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)
- 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)
- 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.

- Computational Bounds for Elevator Control Policies by Large Scale Linear Programming (2013)
- We computationally assess policies for the elevator control problem by a new column-generation approach for the linear programming method for discounted infinite-horizon Markov decision problems. By analyzing the optimality of given actions in given states, we were able to provably improve the well-known nearest-neighbor policy. Moreover, with the method we could identify an optimal parking policy. This approach can be used to detect and resolve weaknesses in particular policies for Markov decision problems.

- Convex hulls of polyominoes (2007)
- 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)
- Es wird die Anzahl der wesentlich verschiedenen Polyominoes der Ordnung n mit minimalem Umfang p(n) bestimmt.