### Refine

#### Year of publication

- 2015 (5) (remove)

#### Document Type

- Doctoral Thesis (5) (remove)

#### Keywords

- Adjoint Method (1)
- Adjungierte Differentialgleichung (1)
- Approximationstheorie (1)
- Berechnungskomplexität (1)
- Binomial (1)
- Buehler (1)
- Calibration (1)
- Combinatorial Optimization (1)
- Computational complexity (1)
- Couple constraints (1)

#### Institute

- Mathematik (5) (remove)

Matching problems with additional resource constraints are generalizations of the classical matching problem. The focus of this work is on matching problems with two types of additional resource constraints: The couple constrained matching problem and the level constrained matching problem. The first one is a matching problem which has imposed a set of additional equality constraints. Each constraint demands that for a given pair of edges either both edges are in the matching or none of them is in the matching. The second one is a matching problem which has imposed a single equality constraint. This constraint demands that an exact number of edges in the matching are so-called on-level edges. In a bipartite graph with fixed indices of the nodes, these are the edges with end-nodes that have the same index. As a central result concerning the couple constrained matching problem we prove that this problem is NP-hard, even on bipartite cycle graphs. Concerning the complexity of the level constrained perfect matching problem we show that it is polynomially equivalent to three other combinatorial optimization problems from the literature. For different combinations of fixed and variable parameters of one of these problems, the restricted perfect matching problem, we investigate their effect on the complexity of the problem. Further, the complexity of the assignment problem with an additional equality constraint is investigated. In a central part of this work we bring couple constraints into connection with a level constraint. We introduce the couple and level constrained matching problem with on-level couples, which is a matching problem with a special case of couple constraints together with a level constraint imposed on it. We prove that the decision version of this problem is NP-complete. This shows that the level constraint can be sufficient for making a polynomially solvable problem NP-hard when being imposed on that problem. This work also deals with the polyhedral structure of resource constrained matching problems. For the polytope corresponding to the relaxation of the level constrained perfect matching problem we develop a characterization of its non-integral vertices. We prove that for any given non-integral vertex of the polytope a corresponding inequality which separates this vertex from the convex hull of integral points can be found in polynomial time. Regarding the calculation of solutions of resource constrained matching problems, two new algorithms are presented. We develop a polynomial approximation algorithm for the level constrained matching problem on level graphs, which returns solutions whose size is at most one less than the size of an optimal solution. We then describe the Objective Branching Algorithm, a new algorithm for exactly solving the perfect matching problem with an additional equality constraint. The algorithm makes use of the fact that the weighted perfect matching problem without an additional side constraint is polynomially solvable. In the Appendix, experimental results of an implementation of the Objective Branching Algorithm are listed.

Die vorliegende Arbeit teilt sich in die zwei titelgebenden Themengebiete. Inhalt des ersten Teils dieser Arbeit ist die Untersuchung der Proximität, also einer gewissen Messung der Nähe, von Binomial- und Poisson-Verteilungen. Speziell wird die uniforme Struktur des Totalvariationsabstandes auf der abgeschlossenen Menge aller Binomial- und Poisson-Verteilungen charakterisiert, und zwar mit Hilfe der die Verteilungen eindeutig bestimmenden zugehörigen Erwartungswerte und Varianzen. Insbesondere wird eine obere Abschätzung des Totalvariationsabstandes auf der Menge der Binomial- und Poisson-Verteilungen durch eine entsprechende Funktion der zugehörigen Erwartungswerte und Varianzen angegeben. Der zweite Teil der Arbeit widmet sich Konfidenzintervallen für Durchschnitte von Erfolgswahrscheinlichkeiten. Eine der ersten und bekanntesten Arbeiten zu Konfidenzintervallen von Erfolgswahrscheinlichkeiten ist die von Clopper und Pearson (1934). Im Binomialmodell werden hier bei bekanntem Stichprobenumfang und Konfidenzniveau Konfidenzintervalle für die unbekannte Erfolgswahrscheinlichkeit entwickelt. Betrachtet man bei festem Stichprobenumfang statt einer Binomialverteilung, also dem Bildmaß einer homogenen Bernoulli-Kette unter der Summationsabbildung, das entsprechende Bildmaß einer inhomogenen Bernoulli-Kette, so erhält man eine Bernoulli-Faltung mit den entsprechenden Erfolgswahrscheinlichkeiten. Für das Schätzen der durchschnittlichen Erfolgswahrscheinlichkeit im größeren Bernoulli-Faltungs-Modell sind z. B. die einseitigen Clopper-Pearson-Intervalle im Allgemeinen nicht gültig. Es werden hier optimale einseitige und gültige zweiseitige Konfidenzintervalle für die durchschnittliche Erfolgswahrscheinlichkeit im Bernoulli-Faltungs-Modell entwickelt. Die einseitigen Clopper-Pearson-Intervalle sind im Allgemeinen auch nicht gültig für das Schätzen der Erfolgswahrscheinlichkeit im hypergeometrischen Modell, das ein Teilmodell des Bernoulli-Faltungs-Modells ist. Für das hypergeometrische Modell mit festem Stichprobenumfang und bekannter Urnengröße sind die optimalen einseitigen Konfidenzintervalle bekannt. Bei festem Stichprobenumfang und unbekannter Urnengröße werden aus den im Bernoulli-Faltungs-Modell optimalen Konfidenzintervallen optimale Konfidenzintervalle für das hypergeometrische Modell entwickelt. Außerdem wird der Fall betrachtet, dass eine obere Schranke für die unbekannte Urnengröße gegeben ist.

In recent years, the study of dynamical systems has developed into a central research area in mathematics. Actually, in combination with keywords such as "chaos" or "butterfly effect", parts of this theory have been incorporated in other scientific fields, e.g. in physics, biology, meteorology and economics. In general, a discrete dynamical system is given by a set X and a self-map f of X. The set X can be interpreted as the state space of the system and the function f describes the temporal development of the system. If the system is in state x âˆˆ X at time zero, its state at time n âˆˆ N is denoted by f^n(x), where f^n stands for the n-th iterate of the map f. Typically, one is interested in the long-time behaviour of the dynamical system, i.e. in the behaviour of the sequence (f^n(x)) for an arbitrary initial state x âˆˆ X as the time n increases. On the one hand, it is possible that there exist certain states x âˆˆ X such that the system behaves stably, which means that f^n(x) approaches a state of equilibrium for nâ†’âˆž. On the other hand, it might be the case that the system runs unstably for some initial states x âˆˆ X so that the sequence (f^n(x)) somehow shows chaotic behaviour. In case of a non-linear entire function f, the complex plane always decomposes into two disjoint parts, the Fatou set F_f of f and the Julia set J_f of f. These two sets are defined in such a way that the sequence of iterates (f^n) behaves quite "wildly" or "chaotically" on J_f whereas, on the other hand, the behaviour of (f^n) on F_f is rather "nice" and well-understood. However, this nice behaviour of the iterates on the Fatou set can "change dramatically" if we compose the iterates from the left with just one other suitable holomorphic function, i.e. if we consider sequences of the form (gâˆ˜f^n) on D, where D is an open subset of F_f with f(D)âŠ‚ D and g is holomorphic on D. The general aim of this work is to study the long-time behaviour of such modified sequences. In particular, we will prove the existence of holomorphic functions g on D having the property that the behaviour of the sequence of compositions (gâˆ˜f^n) on the set D becomes quite similarly chaotic as the behaviour of the sequence (f^n) on the Julia set of f. With this approach, we immerse ourselves into the theory of universal families and hypercyclic operators, which itself has developed into an own branch of research. In general, for topological spaces X, Y and a family {T_i: i âˆˆ I} of continuous functions T_i:Xâ†’Y, an element x âˆˆ X is called universal for the family {T_i: i âˆˆ I} if the set {T_i(x): i âˆˆ I} is dense in Y. In case that X is a topological vector space and T is a continuous linear operator on X, a vector x âˆˆ X is called hypercyclic for T if it is universal for the family {T^n: n âˆˆ N}. Thus, roughly speaking, universality and hypercyclicity can be described via the following two aspects: There exists a single object which allows us, via simple analytical operations, to approximate every element of a whole class of objects. In the above situation, i.e. for a non-linear entire function f and an open subset D of F_f with f(D)âŠ‚ D, we endow the space H(D) of holomorphic functions on D with the topology of locally uniform convergence and we consider the map C_f:H(D)â†’H(D), C_f(g):=gâˆ˜f|_D, which is called the composition operator with symbol f. The transform C_f is a continuous linear operator on the Fréchet space H(D). In order to show that the above-mentioned "nice" behaviour of the sequence of iterates (f^n) on the set D âŠ‚ F_f can "change dramatically" if we compose the iterates from the left with another suitable holomorphic function, our aim consists in finding functions g âˆˆ H(D) which are hypercyclic for C_f. Indeed, for each hypercyclic function g for C_f, the set of compositions {gâˆ˜f^n|_D: n âˆˆ N} is dense in H(D) so that the sequence of compositions (gâˆ˜f^n|_D) is kind of "maximally divergent" " meaning that each function in H(D) can be approximated locally uniformly on D via subsequences of (gâˆ˜f^n|_D). This kind of behaviour stands in sharp contrast to the fact that the sequence of iterates (f^n) itself converges, behaves like a rotation or shows some "wandering behaviour" on each component of F_f. To put it in a nutshell, this work combines the theory of non-linear complex dynamics in the complex plane with the theory of dynamics of continuous linear operators on spaces of holomorphic functions. As far as the author knows, this approach has not been investigated before.

This thesis is divided into three main parts: The description of the calibration problem, the numerical solution of this problem and the connection to optimal stochastic control problems. Fitting model prices to given market prices leads to an abstract least squares formulation as calibration problem. The corresponding option price can be computed by solving a stochastic differential equation via the Monte-Carlo method which seems to be preferred by most practitioners. Due to the fact that the Monte-Carlo method is expensive in terms of computational effort and requires memory, more sophisticated stochastic predictor-corrector schemes are established in this thesis. The numerical advantage of these predictor-corrector schemes ispresented and discussed. The adjoint method is applied to the calibration. The theoretical advantage of the adjoint method is discussed in detail. It is shown that the computational effort of gradient calculation via the adjoint method is independent of the number of calibration parameters. Numerical results confirm the theoretical results and summarize the computational advantage of the adjoint method. Furthermore, provides the connection to optimal stochastic control problems is proven in this thesis.rn

In the first part of this work we generalize a method of building optimal confidence bounds provided in Buehler (1957) by specializing an exhaustive class of confidence regions inspired by Sterne (1954). The resulting confidence regions, also called Buehlerizations, are valid in general models and depend on a designated statistic'' that can be chosen according to some desired monotonicity behaviour of the confidence region. For a fixed designated statistic, the thus obtained family of confidence regions indexed by their confidence level is nested. Buehlerizations have furthermore the optimality property of being the smallest (w.r.t. set inclusion) confidence regions that are increasing in their designated statistic. The theory is eventually applied to normal, binomial, and exponential samples. The second part deals with the statistical comparison of pairs of diagnostic tests and establishes relations 1. between the sets of lower confidence bounds, 2. between the sets of pairs of comparable lower confidence bounds, and 3. between the sets of admissible lower confidence bounds in various models for diverse parameters of interest.