## 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)

228

Weighted k-cardinality trees
(1992)

We consider the k -CARD TREE problem, i.e., the problem of finding in a given undirected graph G a subtree with k edges, having minimum weight. Applications of this problem arise in oil-field leasing and facility layout. While the general problem is shown to be strongly NP hard, it can be solved in polynomial time if G is itself a tree. We give an integer programming formulation of k-CARD TREE, and an efficient exact separation routine for a set of generalized subtour elimination constraints. The polyhedral structure of the convex huLl of the integer solutions is studied.

312

Vigenere-Verschlüsselung
(1999)

322

Integral equations on the half of line are commonly approximated by the finite-section approximation, in which the infinite upper limit is replaced by apositie number called finite-section parameter. In this paper we consider the finite-section approximation for first kind intgral equations which are typically ill-posed and call for regularization. For some classes of such equations corresponding to inverse problems from optics and astronomy we indicate the finite-section parameters that allows to apply standard regularization techniques. Two discretization schemes for the finite-section equations ar also proposed and their efficiency is studied.

296

We show that the occupation measure on the path of a planar Brownian motion run for an arbitrary finite time intervalhas an average density of order three with respect to thegauge function t^2 log(1/t). This is a surprising resultas it seems to be the first instance where gauge functions other than t^s and average densities of order higher than two appear naturally. We also show that the average densityof order two fails to exist and prove that the density distributions, or lacunarity distributions, of order threeof the occupation measure of a planar Brownian motion are gamma distributions with parameter 2.

293

Tangent measure distributions were introduced by Bandt and Graf as a means to describe the local geometry of self-similar sets generated by iteration of contractive similitudes. In this paper we study the tangent measure distributions of hyperbolic Cantor sets generated by contractive mappings, which are not similitudes. We show that the tangent measure distributions of these sets equipped with either Hausdorff or Gibbs measure are unique almost everywhere and give an explicit formula describing them as probability distributions on the set of limit models of Bedford and Fisher.

295

Tangent measure distributions are a natural tool to describe the local geometry of arbitrary measures of any dimension. We show that for every measure on a Euclidean space and every s, at almost every point, all s-dimensional tangent measure distributions define statistically self-similar random measures. Consequently, the local geometry of general measures is not different from the local geometry of self-similar sets. We illustrate the strength of this result by showing how it can be used to improve recently proved relations between ordinary and average densities.

292

Symmetry properties of average densities and tangent measure distributions of measures on the line
(1995)

Answering a question by Bedford and Fisher we show that for every Radon measure on the line with positive and finite lower and upper densities the one-sided average densities always agree with one half of the circular average densities at almost every point. We infer this result from a more general formula, which involves the notion of a tangent measure distribution introduced by Bandt and Graf. This formula shows that the tangent measure distributions are Palm distributions and define self-similar random measures in the sense of U. Zähle.

274

This paper investigates the convergence of the Lanczos method for computing the smallest eigenpair of a selfadjoint elliptic differential operator via inverse iteration (without shifts).
Superlinear convergence rates are established, and their sharpness is investigated for a simple model problem. These results are illustrated numerically for a more difficult problem.

227

Facility location problems in the plane are among the most widely used tools of Mathematical Programming in modeling real-world problems. In many of these problems restrictions have to be considered which correspond to regions in which a placement of new locations is forbidden. We consider center and median problems where the forbidden set is
a union of pairwise disjoint convex sets. As applications we discuss the assembly of printed circuit boards, obnoxious facility location and the location of emergency facilities.

206

In this paper the existence of translation transversal designs which is equivalent to the existence of certain particular partitions in finite groups is studied. All considerations are based on the fact that the particular component of such a partition (the component representing the point classes of the corresponding design) is a normal subgroup of the translation group. With regard to groups admitting an (s,k,\(\lambda\))-partiton, on one hand the already known families of such groups are determined without using R. BAER's, 0.H.KEGEL's and M. SUZUKI' s classification of finite groups with partition and on the other hand some new results on the special structure of p - groups are proved. Furthermore, the existence of a series of nonabelian p - groups of odd order which can be represented as translation groups of certain (s,k,1) - translation transversal designs is shown; moreover, the translation groups are normal subgroups of collineation groups acting regularly on the set of flags of the same designs.

280

This paper develops truncated Newton methods as an appropriate tool for nonlinear inverse problems which are ill-posed in the sense of Hadamard. In each Newton step an approximate solution for the linearized problem is computed with the conjugate gradient method as an inner iteration. The conjugate gradient iteration is terminated when the residual has been reduced to a prescribed percentage. Under certain assumptions on the nonlinear operator it is shown that the algorithm converges and is stable if the discrepancy principle is used to terminate the outer iteration.
These assumptions are fulfilled , e.g., for the inverse problem of identifying the diffusion coefficient in a parabolic differential equation from distributed data.

231

We are concerned with a parameter choice strategy for the Tikhonov regularization \((\tilde{A}+\alpha I)\tilde{x}\) = T* \(\tilde{y}\)+ w where \(\tilde{A}\) is a (not necessarily selfadjoint) approximation of T*T and T*\(\tilde y\)+ w is a perturbed form of the (not exactly computed) term T*y. We give conditions for convergence and optimal convergence rates.

200

Das sind die Texte der Vorlesungen, die ich im Dezember 1988 - März 1989 an der Universität Kaiserslautern hielt. Die Sektionen 1-4 enthalten Materialien, die in Russisch im Buch [33] und in früheren Arbeiten [27,28] [30-33] publiziert sind.
Sektion 5 enthält neue Ergebnisse, die wir während meines Aufenthaltes in Kaiserslautern in Zusammenarbeit mit Herrn Robert Plato
(TU Berlin) ausarbeiteten (siehe [21,22]). Sektion 6 ist eine Erweiterung der Arbeit [31].

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.

338

320

Power-ordered sets are not always lattices. In the case of distributive lattices we give a description by disjoint of chains. Finite power-ordered sets have a polarity. We introduct the leveled lattices and show examples with trivial tolerance. Finally we give a list of Hasse diagrams of power-ordered sets.

284

A polynomial function \(f : L \to L\) of a lattice \(\mathcal{L}\) = \((L; \land, \lor)\) is generated by the identity function id \(id(x)=x\) and the constant functions \(c_a (x) = a\) (for every \(x \in L\)), \(a \in L\) by applying the operations \(\land, \lor\) finitely often. Every polynomial function in one or also in several variables is a monotone function of \(\mathcal{L}\).
If every monotone function of \(\mathcal{L}\)is a polynomial function then \(\mathcal{L}\) is called orderpolynomially complete. In this paper we give a new characterization of finite order-polynomially lattices. We consider doubly irreducible monotone functions and point out their relation to tolerances, especially to central relations. We introduce chain-compatible lattices
and show that they have a non-trivial congruence if they contain a finite interval and an infinite chain. The consequences are two new results. A modular lattice \(\mathcal{L}\) with a finite interval is order-polynomially complete if and only if \(\mathcal{L}\) is finite projective geometry. If \(\mathcal{L}\) is simple modular lattice of infinite length then every nontrivial interval is of infinite length and has the same cardinality as any other nontrivial interval of \(\mathcal{L}\). In the last sections we show the descriptive power of polynomial functions of
lattices and present several applications in geometry.

306

In this paper we study the space-time asymptotic behavior of the solutions and derivatives to th incompressible Navier-Stokes equations. Using moment estimates we obtain that strong solutions to the Navier-Stokes equations which decay in \(L^2\) at the rate of \(||u(t)||_2 \leq C(t+1)^{-\mu}\) will have the following pointwise space-time decay \[|D^{\alpha}u(x,t)| \leq C_{k,m} \frac{1}{(t+1)^{ \rho_o}(1+|x|^2)^{k/2}} \]
where \( \rho_o = (1-2k/n)( m/2 + \mu) + 3/4(1-2k/n)\), and \(|a |= m\). The dimension n is \(2 \leq n \leq 5\) and \(0\leq k\leq n\) and \(\mu \geq n/4\)

224

Jede Wissenschaft entfaltet sich in einem Spannungsverhältnis zu ihren Nachbardisziplinen. In diesem Beitrag wird insbesondere das Disziplinenpaar Mathematik-Philosophie in den Blick genommen. Dies geschieht entlang der Leitfrage, ob und gegebenenfalls wie Philosophie auf die Entwicklung und Ausformung der Mathematik Einfluß genommen hat. Dazu wird nach philosophischen Spuren in der Mathematik gefragt, wobei jene historischen Konstellationen bevorzugt betrachtet werden, die eine grundlegende Änderung im Mathematikverständnis erbracht haben. Deshalb gilt das Hauptinteresse dieser Untersuchung dem Verhältnis von Philosophie und Mathematik in der klassischen Antike, bei Kant und in der Gegenwart.

319

The Kallianpur-Robbins law describes the long term asymptotic behaviour of the distribution of the occupation measure of a Brownian motion in the plane. In this paper we show that this behaviour can be seen at every typical Brownian path by choosing either a random time or a random scale according to the logarithmic laws of order three. We also prove a ratio ergodic theorem for small scales outside an exceptional set of vanishing logarithmic density of order three.

236

Es wird anhand von Beispielen, an denen der Autor in der Vergangenheit gearbeitet hat, gezeigt, wie man Modelle der exakten Naturwissenschaften auf wirtschaftliche Probleme
anwenden kann. Insbesondere wird diskutiert, wo Grenzen dieser Übertragbarkeit liegen. Die Arbeit ist eine Zusammenfassung eines Vortrags, der im SS 1992 im Rahmen des Studium Generale an der Universität Kaiserslautern gehalten wurde.

313

A class of regularization methods using unbounded regularizing operators is considered for obtaining stable approximate solutions for ill-posed operator equations. With an a posteriori as well as an priori parameter choice strategy, it is shown that the method yields optimal order. Error estimates have also been obtained under stronger assumptions on the the generalized solution. The results of the paper unify and simplify many of the results available in the literature. For example, the optimal results of the paper includes, as particular cases for Tikhonov regularization, the main result of Mair (1994) with an a priori parameter choice and a result of Nair (1999) with an a posteriori parameter choice. Thus the observations of Mair (1994) on Tikhonov regularization of ill-posed problems involving finitely and infinitely smoothing operators is applicable to various other regularization procedures as well. Subsequent results on error estimates include, as special cases, an optimal result of Vainikko (1987) and also recent results of Tautenhahn (1996) in the setting Hilbert scales.

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.

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.

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.

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.

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\).

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.

316

205

221