Year of publication
- 2001 (2) (remove)
- 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.
- 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.