## Preprints (rote Reihe) des Fachbereich Mathematik

### Refine

#### Year of publication

#### Keywords

- average density (3)
- tangent measure distributions (3)
- Brownian motion (2)
- Palm distributions (2)
- average densities (2)
- density distribution (2)
- lacunarity distribution (2)
- occupation measure (2)
- order-two densities (2)
- Algebraic Geometry (1)
- Cantor sets (1)
- Complexity (1)
- Complexity and performance of numerical algorithms (1)
- Dirichlet series (1)
- Function of bounded variation (1)
- Hochschild homology (1)
- Hochschild-Homologie (1)
- Homologietheorie (1)
- Ill-Posed Problems (1)
- Improperly posed problems (1)
- Integral transform (1)
- Kallianpur-Robbins law (1)
- Linear Integral Equations (1)
- Local completeness (1)
- Moduli Spaces (1)
- Palm distribution (1)
- Quasi-identities (1)
- Rectifiability (1)
- Riemann-Siegel formula (1)
- Sheaves (1)
- Stratifaltigkeiten (1)
- Translation planes (1)
- Verschlüsselung (1)
- Vigenere (1)
- Zyklische Homologie (1)
- algebraic geometry (1)
- cusp forms (1)
- cyclic homology (1)
- fractals (1)
- geometric measure theory (1)
- geometry of measures (1)
- higher order (1)
- hyper-quasi-identities (1)
- hyperquasivarieties (1)
- intersection local time (1)
- invariant theory (1)
- limit models (1)
- locally maximal clone (1)
- log averaging methods (1)
- logarithmic average (1)
- logarithmic averages (1)
- moduli spaces (1)
- non-commutative geometry (1)
- order-three density (1)
- order-two density (1)
- ovoids (1)
- planar Brownian motion (1)
- preservation of relations (1)
- quadratic forms (1)
- quasivarieties (1)
- ratio ergodic theorem (1)
- singular spaces (1)
- singuläre Räume (1)
- strong theorems (1)

276

Let \(a_1,\dots,a_n\) be independent random points in \(\mathbb{R}^d\) spherically symmetrically but not necessarily identically distributed. Let \(X\) be the random polytope generated as the convex hull of \(a_1,\dots,a_n\) and for any \(k\)-dimensional subspace \(L\subseteq \mathbb{R}^d\) let \(Vol_L(X) :=\lambda_k(L\cap X)\) be the volume of \(X\cap L\) with respect to the \(k\)-dimensional Lebesgue measure \(\lambda_k, k=1,\dots,d\). Furthermore, let \(F^{(i)}\)(t):= \(\bf{Pr}\) \(\)(\(\Vert a_i \|_2\leq t\)),
\(t \in \mathbb{R}^+_0\) , be the radial distribution function of \(a_i\). We prove that the expectation
functional \(\Phi_L\)(\(F^{(1)}, F^{(2)},\dots, F^{(n)})\) := \(E(Vol_L(X)\)) is strictly decreasing in
each argument, i.e. if \(F^{(i)}(t) \le G^{(i)}(t)t\), \(t \in {R}^+_0\), but \(F^{(i)} \not\equiv G^{(i)}\), we show \(\Phi\) \((\dots, F^{(i)}, \dots\)) > \(\Phi(\dots,G^{(i)},\dots\)). The proof is clone in the more general framework
of continuous and \(f\)- additive polytope functionals.

203

The notion of Q-Gorenstein smoothings has been introduced by Kollar. ([KoJ], 6.2.3). This notion is essential for formulating Kollar's conjectures on smoothing components for rational surface singularities. He conjectures, loosely speaking, that every smoothing of a rational surface singularity can be obtained by blowing down a deformation of a partial resolution, this partial resolution having the property (among others) that the singularities occuring on it all have qG-smoothings. (For more details and precise statements see [Ko], ch. 6.). It is therefore of interest to construct singularities having qG-smoothings.

216

We present a generalization of Proth's theorem for testing certain large integers for primality. The use of Gauß sums leads to a much simpler approach to these primality criteria as compared to the earlier tests. The running time of the algorithms is bounded by a polynomial in the length of the input string. The applicability of our algorithms is linked to certain diophantine approximations of \(l\)-adic roots of unity.

266

229

283

The first part of this paper studies a Levenberg-Marquardt scheme for nonlinear inverse problems where the corresponding Lagrange (or regularization) parameter is chosen from an inexact Newton strategy. While the convergence analysis of standard implementations based on trust region strategies always requires the invertibility of the Fréchet derivative of the nonlinear operator at the exact solution, the new Levenberg-Marquardt scheme is suitable for ill-posed problems as long as the Taylor remainder is of second order in the interpolating metric between the range and dornain
topologies. Estimates of this type are established in the second part of the paper for ill-posed parameter identification problems arising in inverse groundwater hydrology. Both, transient and steady state data are investigated. Finally, the numerical performance of the new Levenberg-Marquardt scheme is
studied and compared to a usual implementation on a realistic but synthetic 2D model problem from the engineering literature.

223

Let \(a_1, i:=1,\dots,m\), be an i.i.d. sequence taking values in \(\mathbb{R}^n\), whose convex hull is interpreted as a stochastic polyhedron \(P\). For a special class of random variables, which decompose additively relative to their boundary simplices, eg. the volume of \(P\), simple integral representations of its first two moments are given in case of rotationally symmetric distributions in order to facilitate estimations of variances or to quantify large deviations from the mean.

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.

327

262

Let \(a_1,\dots,a_m\) be i.i .d. vectors uniform on the unit sphere in \(\mathbb{R}^n\), \(m\ge n\ge3\) and let \(X\):= {\(x \in \mathbb{R}^n \mid a ^T_i x\leq 1\)} be the random polyhedron generated by. Furthermore, for linearly independent vectors \(u\), \(\bar u\) in \(\mathbb{R}^n\), let \(S_{u, \bar u}(X)\) be the number of shadow vertices of \(X\) in \(span (u, \bar u\)). The paper provides an asymptotic expansion of the expectation value \(E (S_{u, \bar u})\) for fixed \(n\) and \(m\to\infty\). The first terms of the expansion are given explicitly. Our investigation of \(E (S_{u, \bar u})\) is closely connected to Borgwardt's probabilistic analysis of the shadow vertex algorithm - a parametric variant of the simplex algorithm. We obtain an improved asymptotic upper bound for the number of pivot steps required by the shadow vertex algorithm for uniformly on the sphere distributed data.

305

In this paper we show that for each prime p=7 there exists a translation plane of order p^2 of Mason-Ostrom type. These planes occur as 6-dimensional ovoids being projections of the 8-dimensional binary ovoids of Conway, Kleidman and Wilson. In order to verify the existence of such projections we prove certain properties of two particular quadratic forms using classical methods form number theory.

300

294

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.

302

An a posteriori stopping rule connected with monitoringthe norm of second residual is introduced forBrakhage's implicit nonstationary iteration method, applied to ill-posed problems involving linear operatorswith closed range. It is also shown that for someclasses of equations with such operators the algorithmconsisting in combination of Brakhage's method withsome new discretization scheme is order optimal in the sense of Information Complexity.

339

Caloric Restriction (CR) is the only intervention proven to retard aging and extend maximum lifespan in mammalians. A possible mechanism for the beneficial effects of CR is that the mild metabolic stress associated with CR induces cells to express stress proteins that increase their resistance to disease processes. In this article we therefore model the retardation of aging by dietary restriction within a mathematical framework. The resulting model comprises food intake, stress proteins, body growth and survival. We successfully applied our model to growth and survival data of mice exposed to different food levels.

304

It is proved that if a finite non-trivial quasi-order is nota linear order then there exist continuum many clones, whichconsist of functions preserving the quasi-order and containall unary functions with this property. It is shown that, fora linear order on a three-element set, there are only 7 suchclones

265

In multiple criteria optimization an important research topic is the topological structure of the set \( X_e \) of efficient solutions. Of major interest is the connectedness of \( X_e \), since it would allow the determination of \( X_e \) without considering non-efficient solutions in the
process. We review general results on the subject,including the connectedness result for efficient solutions in multiple criteria linear programming. This result can be used to derive a definition of connectedness for discrete optimization problems. We present a counterexample to a previously stated result in this area, namely that the set of efficient solutions of the shortest path problem is connected. We will also show that connectedness does not hold for another important problem in discrete multiple criteria optimization: the spanning tree problem.

303

We show that the intersection local times \(\mu_p\) on the intersection of \(p\) independent planar Brownian paths have an average density of order three with respect to the gauge function \(r^2\pi\cdot (log(1/r)/\pi)^p\), more precisely, almost surely, \[ \lim\limits_{\varepsilon\downarrow 0} \frac{1}{log |log\ \varepsilon|} \int_\varepsilon^{1/e} \frac{\mu_p(B(x,r))}{r^2\pi\cdot (log(1/r)/\pi)^p} \frac{dr}{r\ log (1/r)} = 2^p \mbox{ at $\mu_p$-almost every $x$.} \] We also show that the lacunarity distributions of \(\mu_p\), at \(\mu_p\)-almost every point, is given as the distribution of the product of \(p\) independent gamma(2)-distributed random variables. The main tools of the proof are a Palm distribution associated with the intersection local time and an approximation theorem of Le Gall.

309

In einem Beitrag zu Platons Philosophie des Abstiegs schreibt C.F. v. Weizsäcker, er sei "überzeugt, daß die griechische Philosophie, dieses in allen Weltkulturen einzigartige Kunstwerk, ohne das mathematische Paradigma undenkbar gewesen wäre" . Und in seiner berühmten Kant-Vorlesung im WS 1935/36 erklärte M. Heidegger, es sei "kein Zufall, daß die Kritik der reinen Vernunft... ständig von einer Besinnung auf das Wesen des Mathematischen und der Mathematik begleitet sei" . Was hier über Platon und Kant gesagt wird, trifft auf fast alle abendländischen Philosophen von Rang zu: Explizit oder implizit spielt die Mathematik eine entscheidende Rolle für die neue philosophische Konzeption. Welche Gründe sind es, die der Mathematik einen so hohen Stellenwert im Denken der maßgebenden Philosophen sichern? Mit welchen Intentionen und Zielvorstellungen montieren Philosophen seit Platon bis Heidegger, seit Aristoteles bis Bloch immer wieder Aussagen über Mathematik in ihre Philosophie? Weshalb war in den vergangenen zweieinhalb Jahrtausenden keine andere Wissenschaft für die Philosophie so >>frag-würdig<< wie die Mathematik? Die Philosophie hat - dies ist offensichtlich - den Dialog mit der Mathematik immer wieder gesucht. Und wie steht es um das Interesse der Mathematik an einem Dialog mit der Philosophie? In einem äußerst gehaltvollen und auch heute noch sehr lesenswerten Aufsatz Mathematik und Antike stellt der Mathematiker O. Toeplitz 1925 die Frage, "ob einmal im Dasein der Mathematik die Philosophie bestimmend in sie eingegriffen hat, ihre eigentliche definitive Gestalt gebildet hat" ? Eine derartige Initiative aus der Mathematik heraus zum Dialog mit der Philosophie ist kein Einzelfall. Cantor, Hilbert, Weyl, Gödel und Robinson - um nur einige Repräsentanten der neueren Mathematik in Erinnerung zu rufen - haben sich immer wieder um Kontakte mit der Philosophie bemüht.

324

275

286

An analogue of the classical Riemann-Siegel integral formula for Dirichlet series associated to cusp forms is developed. As an application of the formula, we give a comparatively simple proof of the approximate functional equation for this type of Dirichlet series.

289

We compare different notions of differentiability of a measure along a vector field on a locally convex space. We consider in the \(L^2\)-space of a differentiable measure the analoga of the classical concepts of gradient, divergence and Laplacian (which coincides with the Ornstein-Uhlenbeck
operator in the Gaussian case). We use these operators for the extension of the basic results of Malliavin and Stroock on the smoothness of finite dimensional image measures under certain nonsmooth mappings to the case of non-Gaussian measures. The proof of this extension is quite direct and does not use any Chaos-decomposition. Finally, the role of this Laplacian in the
procedure of quantization of anharmonic oscillators is discussed.

219

A Remark on Primes of the Form \(2^{3n}a + 2^{2n}b+2^nc+1\). Necessary and sufficient conditions for the numbers in the title to be prime are given. The tests are well suited for practical purposes.

308

In this paper we discuss a special class of regularization methods for solving the satellite gravity gradiometry problem in a spherical framework based on band-limited spherical regularization wavelets. Considering such wavelets as a reesult of a combination of some regularization methods with Galerkin discretization based on the spherical harmonic system we obtain the error estimates of regularized solutions as well as the estimates for regularization parameters and parameters of band-limitation.

279

It is shown that Tikhonov regularization for ill- posed operator equation
\(Kx = y\) using a possibly unbounded regularizing operator \(L\) yields an orderoptimal algorithm with respect to certain stability set when the regularization parameter is chosen according to the Morozov's discrepancy principle. A more realistic error estimate is derived when the operators \(K\) and \(L\) are related to a Hilbert scale in a suitable manner. The result includes known error estimates for ordininary Tikhonov regularization and also the estimates available under the Hilbert scale approach.

297

In the Banach space co there exists a continuous function of bounded semivariation which does not correspond to a countably additive vector measure. This result is in contrast to the scalar case, and it has consequences for the characterization of scalar-type operators. Besides this negative result we introduce the notion of functions of unconditionally bounded variation which are exactly the generators of countably additive vector measures.

332

In recent years a considerable attention was paid to an investigation of finite orders relative to different properties of their isotone functions [2,3]. Strict order relations are defined as strict asymmetric and transitive binary relations. Some algebraic properties of strict orders were already studied in [6]. For the class K of so-called 2-series strict orders we describe the partially ordered set EndK of endomorphism monoids, ordered by inclusion. It is obtained that EndK possesses a least element and in most cases defines a Boolean algebra. Moreover, every 2-series strict order is determined by its n-ary isotone functions for some natural number n.

334

We define a class of topological spaces (LCNT-spaces) which come together with a nuclear Frechet algebra. Like the algebra of smooth functions on a manifold, this algebra carries the differential structure of the object. We compute the Hochschild homology of this object and show that it is isomorphic to the space of differential forms. This is a generalization of a result obtained by Alain Connes in the framework of smooth manifolds.

321

220

Hyperidentities
(1992)

The concept of a free algebra plays an essential role in universal algebra and in computer science. Manipulation of terms, calculations and the derivation of identities are performed in free algebras. Word problems, normal forms, system of reductions, unification and finite bases of identities are topics in algebra and logic as well as in computer science. A very fruitful point of view is to consider structural properties of free algebras. A.I. Malcev initiated a thorough research of the congruences of free algebras. Henceforth congruence permutable, congruence distributive and congruence modular varieties are
intensively studied. A lot of Malcev type theorems are connected to the congruence lattice of free algebras. Here we consider free algebras as semigroups of compositions of terms and more specific as clones of terms. The properties of these semigroups and clones are adequately described by hyperidentities. Naturally a lot of theorems of "semigroup" or "clone" type can be derived. This topic of research is still in its beginning and therefore a lot öf concepts and results cannot be presented in a final and polished form. Furthermore a lot of problems and questions are open which are of importance for the further development of the theory of hyperidentities.

336

Hyperquasivarieties
(2003)

331

Strict order relations are defined as strict asymmetric and transitive binary relations. For classes of so-called levelled strict orders it is analyzed, under which conditions the endomorphism monoids of two relations coincide; in particular the case of direct sums of strict antichains is studied. Further, it is shown that these orders differ in their sets of binary order preserving functions.

268

In this paper we will introduce the concept of lexicographic max-ordering solutions for multicriteria combinatorial optimization problems. Section 1 provides the basic notions of
multicriteria combinatorial optimization and the definition of lexicographic max-ordering solutions. In Section 2 we will show that lexicographic max-ordering solutions are pareto optimal as well as max-ordering optimal solutions. Furthermore lexicographic max-ordering solutions can be used to characterize the set of pareto solutions. Further properties of lexicographic max-ordering solutions are given. Section 3 will be devoted to algorithms. We give a polynomial time algorithm for the two criteria case where one criterion is a sum and one is a bottleneck objective function, provided that the one criterion sum problem is solvable in polynomial time. For bottleneck functions an algorithm for the general case of Q criteria is presented.

254

307

Seinen Versuch, den Begriff der negativen Größen in die Weltweisheit einzuführen beginnt der neununddreißigjährige Immanuel Kant mit einer grundsätzlichen Erörterung über einen etwaigen Gebrauch, den man in der Weltweisheit von der Mathematik ma-chen kann. Dabei stellt er die These auf, daß Mathematik grundsätzlich nur auf zweierlei Art in die Philosophie eingreifen könne. Eine erste Möglichkeit sieht Kant in der Nachahmung mathematischer Methoden bei der Darstellung von Philosophie, die andere Möglichkeit besteht für ihn in der konkreten Anwendung mathematischer Theorien in der Naturlehre. Die zuerst genannte Möglichkeit beurteilt Kant ausgesprochen negativ; seine Kritik an dem von Comenius zunächst ganz allgemein formulierten und dann von Christian Wolff insbesondere für die Philosophie favorisierten Programm einer Präsentation der Philosophie nach mathematischem Vorbild einer Darstellung more geometrico demonstrata ist hinlänglich bekannt. Die Verwendung von Mathematik in der Naturlehre sieht Kant zwar durchaus positiv; in den Metaphysischen Anfangsgründen der Naturwissenschaft wird er gut zwei Jahrzehnte später sogar jene berühmte Behauptung hinzufügen, daß in jeder besonderen Naturlehre nur so viel eigentliche Wissenschaft angetroffen werden könne, als darin Mathematik anzutreffen ist. Dennoch weist Kant mit aller Deutlichkeit auf die engen Grenzen des Wirkungsbereichs solcher Anwendungen von Mathematik hin, denn seiner Meinung nach würden aber auch nur die zur Naturlehre gehörigen Einsichten von derartigem mathematischem Zugriff profitieren.

207

Moduli for singularities
(1991)

The aim of this article is to give a survey on recent results about moduli spaces for curve singularities and for modules over the local ring of a fixed curve singularity. We emphasize especially the general concept which lies behind these constructions.
Therefore, the article might be useful to the reader who wishes to have the leading ideas and the main steps of the proofs explained without going into all the details. We also calculate explicit examples (for singularities and for modules) which illustrate
the general theorems.

301

We extend the methods of geometric invariant theory to actions of non reductive groups in the case of homomorphisms between decomposable sheaves whose automorphism groups are non recutive. Given a linearization of the natural actionof the group Aut(E)xAut(F) on Hom(E,F), a homomorphism iscalled stable if its orbit with respect to the unipotentradical is contained in the stable locus with respect to thenatural reductive subgroup of the automorphism group. Weencounter effective numerical conditions for a linearizationsuch that the corresponding open set of semi-stable homomorphismsadmits a good and projective quotient in the sense of geometricinvariant theory, and that this quotient is in additiona geometric quotient on the set of stable homomorphisms.

330

In this paper we study linear ill-posed problems Ax = y in a Hilbert space setting where instead of exact data y noisy data y^delta are given satisfying |y - y^delta| <= delta with known noise level delta. Regularized approximations are obtained by a general regularization scheme where the regularization parameter is chosen from Morozov's discrepancy principle. Assuming the unknown solution belongs to some general source set M we prove that the regularized approximation provides order optimal error bounds on the set M. Our results cover the special case of finitely smoothing operators A and extends recent results for infinitely smoothing operators.

243

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.

277

A convergence rate is established for nonstationary iterated Tikhonov regularization, applied to ill-posed problems involving closed, densely defined linear operators, under general conditions on the iteration parameters. lt is also shown that an order-optimal accuracy is attained when a certain a posteriori stopping rule is used to determine the iteration number.

208

In this paper we continue the study of p - groups G of square order \(p^{2n}\) and investigate the existence of partial congruence partitions (sets of mutually disjoint subgroups of order \(p^n\)) in G. Partial congruence partitions are used to construct translation nets and partial difference sets, two objects studied extensively in finite geometries and combinatorics. We prove that the maximal number of mutually disjoint subgroups of order \(p^n\) in a group G of order \(p^{2n}\) cannot be more than \((p^{n-1}-1)(p-1)^{-1}\) provided that \(n\ge4\)and that G is not elementary abelian. This improves a result in [6] and as we do not distinguish the cases p=2 and p odd in the present paper, we also have a generalization of D. FROHARDT' s theorem on 2 - groups in [4]. Furthermore we study groups of order \(p^6\). We can show that for each odd prime number, there exist exactly four nonisomorphic groups which contain at least p+2 mutually disjoint subgroups of order \(p^3\). Again, as we do not distinguish between the even and the odd case in advance, we in particular obtain
D. GLUCK' s and A. P. SPRAGUE' s classification of groups of order 64 which contain at least 4 mutually disjoint subgroups of order 8 in [5] and [13] respectively.

201

232

We show that the different module structures of GF(\(q^m\)) arising from the intermediate fields of GF(\(q^m\))and GF(q) can be studied simultaneously with the help of some basic properties of cyclotomic polynomials. We use this ideas to give a detailed and constructive proof of the most difficult part of a Theorem of D. Blessenohl and K. Johnsen (1986), i.e., the existence of elements v in GF(\(q^m\)) over GF(q) which generate normal bases over any intermediate field of GF(\(q^m\)) and GF(q), provided that m is a prime power. Such elements are called completely free in GF(\(q^m\)) over GF(q). We develop a recursive formula for the number of completely free elements in GF(\(q^m\)) over GF(q) in the case where m is a prime power. Some of the results can be generalized to finite cyclic Galois extensions
over arbitrary fields.

285

On derived varieties
(1996)

Derived varieties play an essential role in the theory of hyperidentities. In [11] we have shown that derivation diagrams are a useful tool in the analysis of derived algebras and varieties. In this paper this tool is developed further in order to use it for algebraic constructions of derived algebras. Especially the operator \(S\) of subalgebras, \(H\) of homomorphic irnages and \(P\) of direct products are studied. Derived groupoids from the groupoid \(N or (x,y)\) = \(x'\wedge y'\) and from abelian groups are considered. The latter class serves as an example for fluid algebras and varieties. A fluid variety \(V\) has no derived variety as a subvariety and is introduced as a counterpart for solid varieties. Finally we use a property of the commutator of derived algebras in order to show that solvability and nilpotency are preserved under derivation.

215

267

In this paper we investigate two optimization problems for matroids with multiple objective functions, namely finding the pareto set and the max-ordering problem which conists in finding a basis such that the largest objective value is minimal. We prove that the decision versions of both problems are NP-complete. A solution procedure for the max-ordering problem is presented and a result on the relation of the solution sets of the two problems is given. The main results are a characterization of pareto bases by a basis exchange property and finally a connectivity result for proper pareto solutions.

328

In this short note we prove some general results on semi-stable sheaves on P_2 and P_3 with arbitrary linear Hilbert polynomial. Using Beilinson's spectral sequence, we compute free resolutions for this class of semi-stable sheaves and deduce that the smooth moduli spaces M_{r m + s}(P_2) and M_{r m + r - s}(P_2) are birationally equivalent if r and s are coprime.

239

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.

250

Let (\(a_i)_{i\in \bf{N}}\) be a sequence of identically and independently distributed random vectors drawn from the \(d\)-dimensional unit ball \(B^d\)and let \(X_n\):= convhull \((a_1,\dots,a_n\)) be the random polytope generated by \((a_1,\dots\,a_n)\). Furthermore, let \(\Delta (X_n)\) : = (Vol \(B^d\) \ \(X_n\)) be the deviation of the polytope's volume from the volume of the ball. For uniformly distributed \(a_i\) and \(d\ge2\), we prove that tbe limiting distribution of \(\frac{\Delta (X_n)} {E(\Delta (X_n))}\) for \(n\to\infty\) satisfies a 0-1-law. Especially, we provide precise information about the asymptotic behaviour of the variance of \(\Delta (X_n\)). We deliver analogous results for spherically symmetric distributions in \(B^d\) with regularly varying tail.

218

221

205

316

299

We propose a new discretization scheme for solving ill-posed integral equations of the third kind. Combining this scheme with Morozov's discrepancy principle for Landweber iteration we show that for some classes of equations in such method a number of arithmetic operations of smaller order than in collocation method is required to appoximately solve an equation with the same accuracy.

282

Let \(a_1,\dots,a_m\) be independent random points in \(\mathbb{R}^n\) that are independent and identically distributed spherically symmetrical in \(\mathbb{R}^n\). Moreover, let \(X\) be the random polytope generated as the convex hull of \(a_1,\dots,a_m\) and let \(L_k\) be an arbitrary \(k\)-dimensional
subspace of \(\mathbb{R}^n\) with \(2\le k\le n-1\). Let \(X_k\) be the orthogonal projection image of \(X\) in \(L_k\). We call those vertices of \(X\), whose projection images in \(L_k\) are vertices of \(X_k\)as well shadow vertices of \(X\) with respect to the subspace \(L_k\) . We derive a distribution independent sharp upper bound for the expected number of shadow vertices of \(X\) in \(L_k\).

271

The paper deals with parallel-machine and open-shop scheduling problems with preemptions and arbitrary nondecreasing objective function. An approach to describe
the solution region for these problems and to reduce them to minimization problems on polytopes is proposed. Properties of the solution regions for certain problems are investigated. lt is proved that open-shop problems with unit processing times are equivalent to certain parallel-machine problems, where preemption is allowed at arbitrary time. A polynomial algorithm is presented transforming a schedule of one type into a schedule of the other type.

233

Let \(a_i i:= 1,\dots,m.\) be an i.i.d. sequence taking values in \(\mathbb{R}^n\). Whose convex hull is interpreted as a stochastic polyhedron \(P\). For a special class of random variables which decompose additively relative to their boundary simplices, eg. the volume of \(P\), integral representations of their first two moments are given which lead to asymptotic estimations of variances for special "additive variables" known from stochastic approximation theory in case of rotationally symmetric distributions.