## Preprints (rote Reihe) des Fachbereich Mathematik

246

Max ordering (MO) optimization is introduced as tool for modelling production
planning with unknown lot sizes and in scenario modelling. In MO optimization a feasible solution set \(X\) and, for each \(x\in X, Q\) individual objective functions \(f_1(x),\dots,f_Q(x)\) are given. The max ordering objective
\(g(x):=max\) {\(f_1(x),\dots,f_Q(x)\)} is then minimized over all \(x\in X\).
The paper discusses complexity results and describes exact and approximative
algorithms for the case where \(X\) is the solution set of combinatorial
optimization problems and network flow problems, respectively.

245

Let \(A\):= {\(a_i\mid i= 1,\dots,m\)} be an i.i.d. random sample in (\mathbb{R}^n\), which we consider a random polyhedron, either as the convex hull of the \(a_i\) or as the intersection of halfspaces {\(x \mid a ^T_i x\leq 1\)}. We introduce a class of polyhedral functionals we will call "additive-type functionals", which covers a number of polyhedral functionals discussed in different mathematical fields, where the emphasis in our contribution will be on those, which arise in linear optimization theory. The class of additive-type functionals is a suitable setting in order to unify and to simplify the asymptotic probabilistic analysis of first and second moments of polyhedral functionals. We provide examples of asymptotic results on expectations and on variances.

248

The article provides an asymptotic probabilistic analysis of the variance of the number of pivot steps required by phase II of the "shadow vertex algorithm" - a parametric variant of the simplex algorithm, which has been proposed by Borgwardt [1] . The analysis is done for data which satisfy a rotationally
invariant distribution law in the \(n\)-dimensional unit ball.

238

Despite their very good empirical performance most of the simplex algorithm's variants require exponentially many pivot steps in terms of the problem dimensions of the given linear programming problem (LPP) in worst-case situtation. The first to explain the large gap between practical experience and the disappointing worst-case was Borgwardt (1982a,b), who could prove polynomiality on tbe average for a certain variant of the algorithm-the " Schatteneckenalgorithmus (shadow vertex algorithm)" - using a stochastic problem simulation.

242

Efficient algorithms and structural results are presented for median
problems with 2 new facilities including the classical 2-Median problem,
the 2-Median problem with forbidden regions and bicriterial 2-Median
problems. This is the first paper dealing with multi-facility multiobjective location problems. The time complexity of all presented algorithms is O(MlogM), where M is the number of existing facilities.