## Preprints (rote Reihe) des Fachbereich Mathematik

### Filtern

#### Erscheinungsjahr

- 1993 (12) (entfernen)

#### Dokumenttyp

- Bericht (10)
- Wissenschaftlicher Artikel (1)
- Preprint (1)

#### Sprache

- Englisch (12) (entfernen)

- 248
- On the Variance of the Number of Pivot Steps Required by the Simplex Algorithm (1993)
- 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.

- 245
- A Unified Asymptotic Prohabilistic Analysis of Polyhedral Functionals (1993)
- 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.

- 246
- Ranking Approach to Max-Ordering Combinatorial Optimization and Network Flows (1993)
- 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.

- 240
- Algebraizations with minimal class group (1993)

- 244
- Gröbner Bases in Algebras with Zerodivisors (1993)

- 242
- Bicriterial and restricted planar 2-Median Problems (1993)
- 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.

- 238
- On the Variance of the Number of Pivot Steps Required by the Simplex Algorithm (1993)
- 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.

- 239
- On spanning tree problems with multiple objectives (1993)
- We investigate two versions of multiple objective minimum spanning tree problems defined on a network with vectorial weights. First, we want to minimize the maximum of Q linear objective functions taken over the set of all spanning trees (max linear spanning tree problem ML-ST). Secondly, we look for efficient spanning trees (multi criteria spanning tree problem MC-ST). Problem ML-ST is shown to be NP-complete. An exact algorithm which is based on ranking is presented. The procedure can also be used as an approximation scheme. For solving the bicriterion MC-ST, which in the worst case may have an exponential number of efficient trees, a two-phase procedure is presented. Based on the computation of extremal efficient spanning trees we use neighbourhood search to determine a sequence of solutions with the property that the distance between two consecutive solutions is less than a given accuracy.

- 243
- Multicriterial Planar Location Problems (1993)
- Given Q different objective functions, three types of single-facility problems are considered: Lexicographic, pareto and max ordering problems. After discussing the interrelation between the problem types, a complete characterization of lexicographic locations and some instances of pareto and max ordering locations is given. The characterizations result in efficient solution algorithms for finding these locations. The paper relies heavily on the theory of restricted locations developed by the same authors, and can be further extended, for instance, to multifacility problems with several objectives. The proposed approach is more general than previously published results on multicriteria planar location problems and is particulary suited for modelling real-world problems.