## Report in Wirtschaftsmathematik (WIMA Report)

### Refine

#### Keywords

- Minkowski space (1)
- Optimierung (1)
- Standorttheorie (1)
- Verkehsplanung (1)
- center hyperplane (1)
- centrally symmetric polytope (1)
- common transversal (1)
- consecutive ones property (1)
- hyperplane transversal (1)
- location theory (1)

- 27
- A geometric approach to global optimization (1999)
- In this paper we consider the problem of optimizing a piecewise-linear objective function over a non-convex domain. In particular we do not allow the solution to lie in the interior of a prespecified region R. We discuss the geometrical properties of this problems and present algorithms based on combinatorial arguments. In addition we show how we can construct quite complicated shaped sets R while maintaining the combinatorial properties.

- 6
- A Note on Center Problems with forbidden Polyhedra (1999)
- The problem of finding an optimal location X* minimizing the maximum Euclidean distance to existing facilities is well solved by e.g. the Elzinga-Hearn algorithm. In practical situations X* will however often not be feasible. We therefore suggest in this note a polynomial algorithm which will find an optimal location X^F in a feasible subset F of the plane R^2

- 74
- Anchored hyperplane location problems (2001)
- The anchored hyperplane location problem is to locate a hyperplane passing through some given points P IR^n and minimizing either the sum of weighted distances (median problem), or the maximum weighted distance (center problem) to some other points Q IR^n . If the distances are measured by a norm, it will be shown that in the median case there exists an optimal hyperplane that passes through at least n - k affinely independent points of Q, if k is the maximum number of affinely independent points of P. In the center case, there exists an optimal hyperplane which isatmaximum distance to at least n - k + 1 affinely independent points of Q. Furthermore, if the norm is a smooth norm, all optimal hyperplanes satisfy these criteria. These new results generalize known results about unrestricted hyperplane location problems.

- 47
- Hyperplane transversals of homothetical, centrally symmetric polytopes (1999)
- Let P c R^n, n >= 2, be a centrally symmetric, convex n-polytope with 2r vertices, and P be a family of m >= n + 1 homothetical copies of P. We show that a hyperplane transversal of all members of P (it it exists) can be found in O(rm) time.

- 92
- Integer programming approaches for solving the delay management problem (2004)
- In the delay management problem we decide how to react in case of delays in public transportation. More specific, the question is if connecting vhicles should wait for delayed feeder vehicles or if it is better to depart in time.

- 63
- Linear Facility Location in Three Dimensions - Models and Solution Methods (2000)
- We consider the problem of locating a line or a line segment in three- dimensional space, such that the sum of distances from the linear facility to a given set of points is minimized. An example is planning the drilling of a mine shaft, with access to ore deposits through horizontal tunnels connecting the deposits and the shaft. Various models of the problem are developed and analyzed, and effcient solution methods are given.

- 3
- Locating Least-Distance Lines in the Plane (1999)
- In this paper we deal with locating a line in the plane. If d is a distance measure our objective is to find a straight line l which minimizes f(l) of g(l) (see the paper for the definition of these functions). We show that for all distance measures d derived from norms, one of the lines minimizing f(l) contains at least two of the existing facilities. For the center objective we always get an optimal line which is at maximum distance from at least three of the existing facilities. If all weights are equal, there is an optimal line which is parallel to one facet of the convex hull of the existing facilities.

- 76
- Locating New Stops in a Railway Network (2001)
- Given a railway network together with information on the population and their use of the railway infrastructure, we are considering the e ffects of introducing new train stops in the existing railway network. One e ffect concerns the accessibility of the railway infrastructure to the population, measured in how far people live from their nearest train stop. The second effect we study is the change in travel time for the railway customers that is induced by new train stops. Based on these two models, we introduce two combinatorial optimization problems and give NP-hardness results for them. We suggest an algorithmic approach for the model based on travel time and give first experimental results.

- 86
- Locating stops along bus or railway lines - a bicriterial problem (2003)
- In this paper we consider the location of stops along the edges of an already existing public transportation network, as introduced in [SHLW02]. This can be the introduction of bus stops along some given bus routes, or of railway stations along the tracks in a railway network. The goal is to achieve a maximal covering of given demand points with a minimal number of stops. This bicriterial problem is in general NP-hard. We present a nite dominating set yielding an IP-formulation as a bicriterial set covering problem. We use this formulation to observe that along one single straight line the bicriterial stop location problem can be solved in polynomial time and present an e cient solution approach for this case. It can be used as the basis of an algorithm tackling real-world instances.

- 18
- Median hyperplanes in normed spaces (1999)
- In this paper we deal with the location of hyperplanes in n-dimensional normed spaces. If d is a distance measure, our objective is to find a hyperplane H which minimizes f(H) = sum_{m=1}^{M} w_{m}d(x_m,H), where w_m ge 0 are non-negative weights, x_m in R^n, m=1, ... ,M demand points and d(x_m,H)=min_{z in H} d(x_m,z) is the distance from x_m to the hyperplane H. In robust statistics and operations research such an optimal hyperplane is called a median hyperplane. We show that for all distance measures d derived from norms, one of the hyperplanes minimizing f(H) is the affine hull of n of the demand points and, moreover, that each median hyperplane is (ina certain sense) a halving one with respect to the given point set.