## Preprints (rote Reihe) des Fachbereich Mathematik

### Refine

#### Document Type

- Report (78) (remove)

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.