Search

Order reduction methods are important tools for systems engineering and can be used, for example, for parameter estimation of kinetic models for systems biology applications. In particular, the Proper Orthogonal Decomposition (POD) method produces a reduced-order model of a system that is used for solving inverse problems (parameter estimation). POD is an intrusive model order reduction method that is aimed to obtain a lower-dimensional system for a high-dimensional system while preserving the main features of the original system. We use a singular value decomposition (SVD) to compute a reduced basis as it is usually numerically more robust to compute the singular values of the snapshot matrix instead of the eigenvalues of the corresponding correlation matrix. The reduced basis functions are then used to construct a data-fitting function that fits a known experimental data set of system substance concentrations. The method is applied to calibrate a kinetic model of carbon catabolite repression (CCR) in Escherichia coli, where the regulatory mechanisms on the molecular side are well understood and experimental data for a number of state variables is available. In particular, we show that the method can be used to estimate the uptake rate constants and other kinetic parameters of the CCR model.

We consider the numerical solution of the discrete multi-marginal optimal transport (MOT) by means of the Sinkhorn algorithm. In general, the Sinkhorn algorithm suffers from the curse of dimensionality with respect to the number of marginals. If the MOT cost function decouples according to a tree or circle, its complexity is linear in the number of marginal measures. In this case, we speed up the convolution with the radial kernel required in the Sinkhorn algorithm via non-uniform fast Fourier methods. Each step of the proposed accelerated Sinkhorn algorithm with a tree-structured cost function has a complexity of O(KN) instead of the classical O(KN2) for straightforward matrix–vector operations, where K is the number of marginals and each marginal measure is supported on, at most, N points. In the case of a circle-structured cost function, the complexity improves from O(KN3) to O(KN2). This is confirmed through numerical experiments.

The dichromatic number $\overrightarrow{\chi }(D)$ of a digraph $D$ is the smallest $k$ for which it admits a $k$-coloring where every color class induces an acyclic subgraph. Inspired by Hadwiger's conjecture for undirected graphs, several groups of authors have recently studied the containment of complete directed minors in digraphs with a given dichromatic number. In this note we exhibit a relation of these problems to Hadwiger's conjecture. Exploiting this relation, we show that every directed graph excluding the complete digraph ${\overleftrightarrow{K}}_{t}$ of order $t$ as a strong minor or as a butterfly minor is $O(t{(\mathrm{log}\unicode{x0200A}\mathrm{log}\unicode{x0200A}t)}^{6})$-colorable. This answers a question by Axenovich, Girao, Snyder, and Weber, who proved an upper bound of $t{4}{t}$ for the same problem. A further consequence of our results is that every digraph of dichromatic number $22n$ contains a subdivision of every $n$-vertex subcubic digraph, which makes progress on a set of problems raised by Aboulker, Cohen, Havet, Lochet, Moura, and Thomasse., Journal of Graph Theory, 101 (4), ISSN:0364-9024, ISSN:1097-0118

In this paper, we for the first time obtain characterization of four fundamental notions of detectability for general labeled weighted automata over monoids (denoted by $\mathcal{A}^{\mathfrak{M}}$ for short), where the four notions are strong (periodic) detectability (SD and SPD) and weak (periodic) detectability (WD and WPD). Firstly, we formulate the notions of concurrent composition, observer, and detector for $\mathcal{A}^{\mathfrak{M}}$. Secondly, we use the concurrent composition to give an equivalent condition for SD, use the detector to give an equivalent condition for SPD, and use the observer to give equivalent conditions for WD and WPD, all for general $\mathcal{A}^{\mathfrak{M}}$ without any assumption. Thirdly, we prove that for a labeled weighted automaton over monoid $(\mathbb{Q}^k,+)$ (denoted by $\mathcal{A}^{\mathbb{Q}^k}$), its concurrent composition, observer, and detector can be computed in NP, $2$-EXPTIME, and $2$-EXPTIME, respectively, by developing novel connections between $\mathcal{A}^{\mathbb{Q}^k}$ and the NP-complete exact path length problem (proved by [Nyk\"{a}nen and Ukkonen, 2002]) and a subclass of Presburger arithmetic. As a result, we prove that for $\mathcal{A}^{\mathbb{Q}^k}$, SD can be verified in coNP, while SPD, WD, and WPD can be verified in $2$-EXPTIME. Finally, we prove that the problems of verifying SD and SPD of deterministic, deadlock-free, and divergence-free $\mathcal{A}^{\mathbb{N}}$ over monoid $(\mathbb{N},+)$ are both coNP-hard. The developed original methods will provide foundations for characterizing other fundamental properties (e.g., diagnosability, opacity) for $\mathcal{A}^{\mathfrak{M}}$. We also initially explore detectability in labeled timed automata, and prove that the SD verification problem is PSPACE-complete, while WD and WPD are undecidable., Comment: 64 pages, 25 figures

A decision support system relies on frequent re-solving of similar problem instances. While the general structure remains the same in corresponding applications, the input parameters are updated on a regular basis. We propose a generative neural network design for learning integer decision variables of mixed-integer linear programming (MILP) formulations of these problems. We utilise a deep neural network discriminator and a MILP solver as our oracle to train our generative neural network. In this article, we present the results of our design applied to the transient gas optimisation problem. The trained generative neural network produces a feasible solution in 2.5s, and when used as a warm start solution, decreases global optimal solution time by 60.5%.

We present impedance boundary conditions for the viscoacoustic equations for approximative models that are in terms of the acoustic pressure or in terms of the macroscropic acoustic velocity. The approximative models are derived by the method of multiple scales up to order 2 in the boundary layer thickness. The boundary conditions are stable and asymptotically exact, which is justified by a complete mathematical analysis. The models can be discretized by finite element methods without resolving boundary layers. In difference to an approximation by asymptotic expansion for which for each order 1 PDE system has to be solved, the proposed approximative are solutions to one PDE system only. The impedance boundary conditions for the pressure of first and second orders are of Wentzell type and include a second tangential derivative of the pressure proportional to the square root of the viscosity and take thereby absorption inside the viscosity boundary layer of the underlying velocity into account. The conditions of second order incorporate with curvature the geometrical properties of the wall. The velocity approximations are described by Helmholtz‐like equations for the velocity, where the Laplace operator is replaced by ∇div, and the local boundary conditions relate the normal velocity component to its divergence. The velocity approximations are for the so‐called far field and do not exhibit a boundary layer. Including a boundary corrector, the so‐called near field, the velocity approximation is accurate even up to the domain boundary. The results of numerical experiments illustrate the theoretical foundations.

We introduce a new class of stochastic partial differential equations (SPDEs) with seed bank modeling the spread of a beneficial allele in a spatial population where individuals may switch between an active and a dormant state. Incorporating dormancy and the resulting seed bank leads to a two-type coupled system of equations with migration between both states. We first discuss existence and uniqueness of seed bank SPDEs and provide an equivalent delay representation that allows a clear interpretation of the age structure in the seed bank component. The delay representation will also be crucial in the proofs. Further, we show that the seed bank SPDEs give rise to an interesting class of “on/off”-moment duals. In particular, in the special case of the F-KPP Equation with seed bank, the moment dual is given by an “on/off-branching Brownian motion”. This system differs from a classical branching Brownian motion in the sense that independently for all individuals, motion and branching may be “switched off” for an exponential amount of time after which they get “switched on” again. On/off branching Brownian motion shows qualitatively different behaviour to classical branching Brownian motion and is an interesting object for study in itself. Here, as an application of our duality, we show that the spread of a beneficial allele, which in the classical F-KPP Equation, started from a Heaviside intial condition, evolves as a pulled traveling wave with speed $$\sqrt{2}$$ 2 , is slowed down significantly in the corresponding seed bank F-KPP model. In fact, by computing bounds on the position of the rightmost particle in the dual on/off branching Brownian motion, we obtain an upper bound for the speed of propagation of the beneficial allele given by $$\sqrt{\sqrt{5}-1}\approx 1.111$$ 5 - 1 ≈ 1.111 under unit switching rates. This shows that seed banks will indeed slow down fitness waves and preserve genetic variability, in line with intuitive reasoning from population genetics and ecology.

Artificial neural networks are at the heart of some of the greatest advances in modern technology. They enable huge breakthroughs in applications ranging from computer vision via machine translation to speech recognition as well as autonomous driving and many more. However, we are still far away from a more rigorous theoretical explanation of these overwhelming success stories. Consequently, the development of a better mathematical understanding of neural networks is currently one of the hottest research topics in computer science. In this thesis we provide several contributions in that direction for the simple, but practically powerful and widely used model of feedforward neural networks with rectified linear unit (ReLU) activations. Our focus is on various notions of what we call the complexity of such neural networks: how much computing resources (time, hardware, network size, etc.) are required to achieve a certain goal? Of course, such questions can be asked in various contexts. We identify and study the following three facets of complexity for neural networks with ReLU activations. The first facet is neural networks' expressivity: What functions can be represented by certain neural network architectures? Even though this is such a fundamental question, very little is known so far. We make progress concerning the question whether the class of exactly representable functions strictly increases by adding more layers (with no restrictions on size). We also provide upper bounds on the number of neurons required to represent arbitrary piecewise linear functions with small-depth ReLU neural networks. The second facet is neural networks' computational power. Here, we view neural networks as a model of computation, just like Boolean, or even closer, arithmetic circuits. We then investigate which network (or circuit) size is required to solve various problems, with a focus on combinatorial optimization problems. Even though this model is quite restrictive compared to other models of computation, we are able to show that comparably small neural networks can provably solve problems like the efficiently solvable Maximum Flow Problem or the NP-hard Knapsack Problem. The third facet is neural networks' training complexity: How difficult is it to fit the weights of a neural network to training data? It is widely known that optimal solutions to the training problem are hard to obtain, which is why local optimization techniques like stochastic gradient descent are used in practice. We focus on the question whether the situation improves for fixed input dimension, leading to the paradigm of parameterized complexity analysis. We provide running time lower bounds in terms of W[1]-hardness results, proving that known brute-force strategies are essentially optimal. On the positive side, we extend a known polynomial-time algorithm for constant dimension and convex loss functions to a more general class of loss functions. The mathematical methods used in this thesis include polyhedral theory, discrete and tropical geometry, mixed-integer and combinatorial optimization, as well as tools from complexity theory., Künstliche neuronale Netze sind der Schlüssel zu einigen der größten modernen Technologiefortschritten. Sie ermöglichen Durchbrüche in Anwendungen wie Computer Vision, maschinellem Übersetzen, Spracherkennung, bis hin zu autonomem Fahren und vielem mehr. Allerdings sind wir nach wie vor weit entfernt von rigorosen theoretischen Erklärungen dieser überwältigenden Erfolge. Daher ist die Entwicklung eines besseren mathematischen Verständnisses neuronaler Netze aktuell eines der wichtigsten Forschungsthemen der Informatik. In dieser Arbeit präsentieren wir einige Fortschritte in diese Richtung für das einfache, aber aus praktischer Sicht mächtige und viel verwendete Modell der Feedforward-Netze mit ReLU-Aktivierungsfunktionen. Unser Fokus liegt auf verschiedenen Arten der Komplexität solcher neuronalen Netze: Wie viele Ressourcen (Zeit, Hardware, Netzwerkgröße etc.) werden benötigt, um ein bestimmtes Ziel zu erreichen? Selbstverständlich können solche Fragen in verschiedenen Kontexten gestellt werden. Wir identifizieren und untersuchen die folgenden drei Facetten der Komplexität für neuronale Netze mit ReLU-Aktivierungsfunktionen. Die erste Facette ist Expressivität: Welche Funktionen können von bestimmten Netzwerkarchitekturen dargestellt werden? Obwohl es sich dabei um eine so fundamentale Frage handelt, ist bisher wenig bekannt. Wir präsentieren Fortschritte bezüglich der Frage, ob die Menge der exakt darstellbaren Funktionen echt größer wird, wenn wir mehr Schichten hinzufügen (ohne dabei die Größe zu beschränken). Wir beweisen außerdem obere Schranken an die Anzahl benötigter Neuronen, um beliebige stückweise lineare Funktionen mit neuronalen Netzen mit geringer Tiefe zu berechnen. Die zweite Facette ist Berechnungskomplexität (Computational Power). Dafür betrachten wir neuronale Netze als ein Berechenbarkeitsmodell, ähnlich wie etwa Boolesche oder arithmetische Schaltkreise. Wir untersuchen, welche Netzwerkgröße nötig ist, um verschiedene Probleme, insbesondere aus der kombinatorischen Optimierung, zu lösen. Trotz der starken Eingeschränktheit dieses Modells zeigen wir, dass vergleichsweise kleine Netze beweisbar Lösungen für Probleme wie das Maximalflussproblem oder das NP-schwere Rucksackproblem finden können. Die dritte Facette ist Trainingskomplexität: Wie schwer ist es, die Gewichte eines neuronalen Netzes an Trainingsdaten anzupassen? Bekanntermaßen ist das Finden exakter Lösungen ein schweres Problem, weshalb in der Praxis lokale Optimierungsverfahren wie etwa stochastischer Gradientenabstieg verwendet werden. Wir beschäftigen uns damit, ob sich die Lage für fixe Dimension verbessert, was uns zum Paradigma der parametrisierten Komplexität führt. Wir beweisen untere Laufzeitschranken in Form von W[1]-Härteresultaten, woraus folgt, dass bekannte Brute-Force-Strategien im Wesentlichen optimal sind. Auf der positiven Seite erweitern wir einen bekannten Polynomialzeitalgorithmus für konstante Dimension und konvexe Lossfunktionen auf eine allgemeinere Klasse von Lossfunktionen. Die in dieser Arbeit verwendeten mathematischen Methoden umfassen Polyedertheorie, diskrete und tropische Geometrie, gemischt-ganzzahlige und kombinatorische Optimierung sowie Tools aus der Komplexitätstheorie.

This thesis analyses three problems from discrete geometry and optimization via discreteanalytic hybrid methods. The absolute value equation (AVE) is a piecewise linear system which is equivalent to the linear complementarity problem (LCP) and thus generalizes linear and quadratic programming. Unique solvability for arbitrary right-hand sides has long been comprehensively characterized for both systems, but not non-unique solvability. To fill this gap in the theory, we analyze homotopies of the identity map and the piecewise linear function corresponding to the AVE. Doing so, we identify certain real eigenvalues of the coefficient matrix of the AVE that determine the singularity-structure of these homotopies. Let k be the number of these eigenvalues which is larger than one. We prove that the mapping degree of the aforementioned piecewise linear function is congruent to (k +1)mod 2. We also derive an exact formula for the degree, which is more technical. Finally, we develop the analogous results for the LCP. The calibration of internal combustion engines is a problem that has risen to prominence during the so-called diesel crisis. Engine behavior can be modeled as a function from the space of actuators to the space of performance measurands. A calibration solution is a set of lookup tables that associate performance demands to points in the actuator space which achieve these demands, while respecting side constraints such as emission standards. We develop an adaptive multigrid method for identifying and circumventing loci of turbulence, which are the cause of emission spikes during the generation of the lookup tables. With the resulting algorithm we calibrate a benchmark engine model in accordance with several EURO emission norms. Dürer’s problem asks whether every 3-polytope has a net, that is, whether it is possible to cut it along some spanning tree of its edge graph so that the resulting connected surface may be unfolded flat into the plane without self-overlaps. A 3-prismatoid is the convex hull of two polygons A, B in parallel planes HA and HB. It is called nested if the orthogonal projection of A to HB is properly contained in B, or vice versa. We show that every nested prismatoid has a net. To this end we adapt and extend an unfolding technique pioneered by O’Rourke in his work on nearly flat, acutely triangulated convex caps. The basic approach is to project a nested prismatoid P—a convex cap by definition—to the plane HB, establish a cutting scheme for the flat polytope, lift the scheme back into P, and then prove that a certain continuous deformation of the unfolding of the flat polytope into the unfolding of P does not cause overlaps., Diese Arbeit behandelt drei Probleme aus der diskreten Geometrie und Optimierung mittels diskret-analytischer Hybridmethoden. Die Absolutwertgleichung (AWG) ist ein stückweise lineares Gleichungssystem, das äquivalent zum linearen Komplementaritätsproblem (LCP) ist und daher lineare und quadratische Programmierung generalisiert. Die vollständige Charakterisierung eindeutiger Lösbarkeit von AWG und LCP für beliebige rechte Seiten sind klassische Resultate der Literatur. Eine vergleichbare Charakterisierung der nicht-eindeutigen Lösbarkeit existiert jedoch nicht. Um diese Lücke in der Theorie zu schließen, analysiseren wir Homotopien der Identitätsabbildung und der stückweise linearen Funktion, welche durch die AWG definiert wird. Hierbei identifizieren wir bestimmte reelle Eigenwerte der Koeffizientenmatrix der AWG, welche die Singulariätsstruktur der untersuchten Homotopien determinieren. Es sei k die Zahl der besagten Eigenwerte, welche größer als eins sind. Wir beweisen, dass in diesem Fall der Abbildungsgrad der stückweise linearen Funktion, welche der AWG korrespondiert, kongruent zu (k + 1)mod 2 ist. Desweiteren leiten wir eine exakte Formel für den Abbildungsgrad her. Schließlich entwickeln wir die analogen Ergebnisse für das LCP. Die Kalibrierung von Verbrennungsmotoren ist ein Problem, das während der sogenannten Dieselkrise zur Prominenz gelangte. Das Motorenverhalten kann als eine Funktion vom Raum der Aktuatoren in den Raum der Leistungsmesswerte modelliert werden. Eine Kalibrierungslösung ist ein Satz von Lookup-Tabellen, die einer Menge von Leistungsanforderungen eine Menge von Punkten im Aktuatorenraum zuordnet, welche besagte Anforderungen, unter Berücksichtigung von Nebenbedingungnen wie z.B. Emissionsgrenzen, realisieren. Wir entwickeln ein adaptives Mehrgitterverfahren um bei der Erstellung der Kalibrierungslösung Regionen stark nichtlinearen Motorenverhaltens im Aktuatorenraum, welche eine Hauptursache von Emissionsspitzen sind, zu identifizieren und zu umgehen. Mittels des resultierenden Algorithmus kalibrieren wir ein Benchmark-Motorenmodell unter Einhaltung verschiedener EURO-Abgasnormen. Dürers Problem stellt die Frage, ob jedes 3-Polytop ein Netz hat, das heißt, ob man es entlang eines Spannbaums seines Kantengraphen aufschneiden kann, so dass die resultierende zusammenhängende Fläche ohne Selbstüberlappungen in die Ebene aufgefaltet werden kann. Ein 3-Prismatoid ist die konvexe Hülle zweier Polygone in parallelen Ebenen HA und HB. Es wird verschachtelt genannt, falls die orthogonale Projektion von A auf HB echt in B enthalten ist. Wir beweisen, dass jedes verschachtelte Prismatoid ein Netz hat. Hierzu adaptieren und erweitern wir eine Auffaltungsstrategie, die von O’Rourke eingeführt wurde. Der Grundgedanke ist, ein verschachteltes Prismatoid P nach HB zu projizieren, ein Schnittschema für das flache Polytop einzuführen, nach P zurück zu projizieren und dann zu beweisen, dass eine bestimmte stetige Verformung der Auffaltung des flachen Polytops in die Auffaltung von P nicht zu Überlappungen führt.

Network flows can be used to model numerous real world applications, such as flows in physical networks like electrical, gas, or water networks, flows in traffic networks, or flows of goods in logistic networks. More precisely, many of these applications can be modeled either as minimum cost flows or equilibria of network games, sometimes even both. In this thesis, we study the computational complexity of computing these flows and develop algorithms solving this task. In contrast to the basic static flow models that are widely studied in the literature, we mainly focus on parametric flow models. In particular, we consider settings where the demands, i.e., the external in- and outflow rates, are parametrized by a one-dimensional value. The solution to a parametric flow problem is no longer one static flow but a function mapping the parameter to a static flow satisfying the respective demands. The parametric model allows to analyze the sensitivity of static flows with respect to the in- and outflow. This thesis is subdivided into two parts. The first part is concerned with the minimum cost flow problem with convex costs, with and without parametric demands. We characterize optimal solutions via optimal potentials, analyze the parametric minimum cost flows and its derivatives, and develop an output-polynomial algorithm that can compute solution functions to the parametric minimum cost flow problem for piecewise quadratic cost functions. We extend the algorithm such that it can also be used to approximate the parametric solution for the minimum cost flow problem with more general, convex costs. Since our algorithms can handle the undirected and directed setting, it can be applied to many real-world problems. In a computational study, we test two different algorithms for the computation of parametric minimum cost flows on several traffic and gas instances and find that the algorithms are also applicable in practice. In the second part, we study the parametric computation of Nash equilibria in an atomic splittable congestion games, a special form of network congestion games. We characterize equilibria and show that their computation is a PPAD-complete problem. As a byproduct of our analysis, we also obtain algorithms for the parametric and non-parametric computation of equilibria in atomic splittable congestion games., Netzwerkflüsse können zur Modellierung zahlreicher Anwendungen verwendet werden, zum Beispiel für Flüsse in physikalischen Netzwerken wie Strom-, Gas- oder Wassernetzen, Flüsse in Verkehrsnetzwerken oder Warenflüsse in logistischen Netzwerken. Genauer gesagt können viele dieser Anwendungen entweder als minimale Kostenflüsse oder Gleichgewichte von Netzwerkspielen modelliert werden, manchmal sogar beides. In dieser Arbeit untersuchen wir die Komplexität der Berechnung dieser Flüsse und entwickeln Algorithmen für deren Berechnung. Im Gegensatz zu statischen Flussmodellen, die in der Literatur häufig untersucht werden, konzentrieren wir uns hauptsächlich auf parametrische Flussmodelle. Insbesondere betrachten wir Modelle, bei denen die Nachfragewerte an den Knoten, das heißt die externen Ein- und Ausflussraten, durch einen eindimensionalen Wert parametrisiert sind. Die Lösung eines parametrischen Flussproblems ist nicht mehr ein statischer Fluss, sondern eine Funktion, die jeden Parameter auf einen statischen Fluss für die entsprechende Nachfragen abbildet. Das parametrische Modell erlaubt es, die Sensitivität von statischen Flüssen in Bezug auf den Ein- und Ausfluss zu analysieren. Diese Arbeit gliedert sich in zwei Teile. Der erste Teil befasst sich mit dem minimalen Kostenflussproblem mit konvexen Kosten, sowohl mit und ohne parametrische Nachfragen. Wir charakterisieren optimale Lösungen über optimale Potentiale, analysieren die parametrischen minimalen Kostenflüsse und ihre Ableitungen und entwickeln einen output-polynomialen Algorithmus, der Lösungsfunktionen für das parametrische minimale Kostenflussproblem für stückweise quadratische Kostenfunktionen berechnen kann. Wir erweitern den Algorithmus, sodass er auch zur Approximation von parametrischen Lösungen für das minimale Kostenflussproblem mit allgemeineren, konvexen Kosten verwendet werden kann. Da unsere Algorithmen sowohl für ungerichtete als auch für gerichtete Netzwerke geeignet ist, kann er auf viele reale Probleme angewendet werden. In einer Rechenstudie testen wir zwei verschiedene Algorithmen auf mehreren Verkehrs- und Gasinstanzen und zeigen, dass die Algorithmen auch in der Praxis anwendbar sind. Im zweiten Teil untersuchen wir die parametrische Berechnung von Nash-Gleichgewichten in atomaren, teilbaren Auslastungsspiele (atomic splittable congestion games), einer speziellen Form von Netzwerkstauspielen. Wir charakterisieren Gleichgewichte und zeigen, dass ihre Berechnung ein PPAD-vollständiges Problem ist. Als Nebenprodukt unserer Analyse erhalten wir auch Algorithmen für die parametrische und nicht-parametrische Berechnung von Gleichgewichten.

In this thesis, we use techniques from polyhedral geometry and statistics in order to detect and quantify biological interactions within a system of genes or species described by a given data set. Our concept relies on the theory of regular subdivisions. A regular subdivision decomposes a space into convex cells and can be used to showcase some distinct aspects of the given data set in its cell structure. After all, one can implement and compute with regular subdivisions and this is an important feature of polyhedral and discrete geometry. The way these cells spatially relate to each other is exploited to determine a list of moderate length with potentially significant biological interactions. A statistical test allows us to diminish this list further and to point to few but statistically significant interactions. A major benefit of our method, and in a way this is reciprocal compared to other existing methods, is the concise extent of our findings which allows for communicating them in a comprehensive form, for instance in data tables or specifically developed bar diagrams. We applied our methods to several experimentally obtained genetic and microbiome data sets. A central use case was the analysis of two instances of Drosophila melanogaster fly gut microbiome studies. The gut of these fruit flies has a microbiome with a small number of constituting species and can be manipulated in the laboratory by regulation of the food. The two Drosophila data sets we applied our methods on describe a microbiome system with five species and hence each of the two data sets can be related to some regular subdivision of the 5-dimensional 0/1-cube from where our method departs. We are able to point to significant higher dimensional interactions which are not perceived by other existing methods and, in particular, are not captured by looking at pairs of interacting species only. Further, we reinterpret and analyze our method mathematically. It produces and is in some way equivalent to naming a network of shortest genetic distances, i.e. a minimum spanning tree of a certain fixed weighted graph with biological meaning. Tropical hypersurfaces, central objects of tropical geometry, which is an active field of research at the border of polyhedral, discrete and algebraic geometry, encapsulate these structures inside their 1-dimensional skeleton. We determine the parameter space of the minimum spanning trees arising this way. It turns out to be encoded by a collection of cones given by linear hyperplanes. For a few elected examples we computed an explicit representation of all occuring parameter cones. Yet, this rapidly reaches limits of complexity. The rest of this thesis is about an achievement beyond these limits. Given a cell decomposition in some implicit form, one may not be able to recuperate the defining geometric data for every cell. But it still may be possible to enumerate them. We present a method for computing the number of chambers of a hyperplane arrangement in real euclidean space which uses purely combinatorial techniques and which makes use of the combinatorial symmetries of the given hyperplane arrangement. With this method, it was possible to compute the previously unknown number of chambers of the ninth resonance arrangement given by 511 hyperplanes in R^9., In dieser Arbeit werden Techniken aus der polyedrischen Geometrie und der Statistik vorgestellt, die benutzt werden können, um biologische Wechselwirkungen in einem durch Datensätze beschriebenen Gen- oder Speziensystem aufzufinden und zu quantifizieren. Unser Konzept beruht auf der Theorie der regulären Unterteilungen. Eine reguläre Unterteilung zerlegt einen Raum in konvexe Zellen, die im vorliegenden Fall dazu dienen, ausgewiesene Eigenschaften der zugrundeliegenden Daten aufzuzeigen. Desweiteren lassen sich reguläre Unterteilungen in Computerprogrammen implementieren und berechnen, was allgemein einen wichtigen Aspekt der polyedrischen und diskreten Geometrie darstellt. Der räumliche Bezug der Zellen zueinander wird hierbei benutzt, um eine Liste angemessener Länge mit potenziell signifikanten biologischen Wechselwirkungen zu erstellen. Desweiteren dient ein statistischer Signifikanztest zur weiteren Ausdünnung dieser Liste, die schließlich nur noch statistisch nachweißbar signifikante Wechselwirkungen enthält. Durch die Bündelung und Konzentration auf relevante Wechselwirkungen zeichnet sich unsere Methode wesentlich aus, da dies sich durchaus konträr zu den bereits existierenden Methoden verhält und eine stringente Kommunikation der Ergebnisse gestattet, beispielsweise in Form von Datentabellen oder eigens konzipierter Bardiagramme. Wir haben unsere Methode auf mehrere Experimentaldatensätze mit Genetik- und Mikrobiombezug angewandt. Ein zentraler Anwendungsfall stellte dabei die Analyse zweier Datensätze dar, die das Mikrobiom des Magens der Drosophila melanogaster Fliege experimentell erfassen. Das Mikrobiom des Magens dieser Fruchtfliege hat die besondere Eigenschaft, durch eine geringe Anzahl von teilhabenden Spezien bestimmt und im Labor leicht manipulierbar zu sein, etwa durch Regulierung des Futters. Die zwei Drosophila Datensätze, die wir betrachteten, beschreiben jeweils ein Mikrobiomsystem mit fünf konstituierenden Spezien und können folglich mit regulären Unterteilungen des fünfdimensionalen 0/1-Würfels assoziiert werden, welche die von uns entwickelte Methode verarbeitet. Es war uns möglich, höherdimensionale Wechselwirkungen zu finden, die von den bereits existierenden Methoden nicht gesehen werden und insbesondere vom Paarvergleich wechselwirkender Spezien übergangen werden. Desweiteren interpretieren und analysieren wir unsere biologisch motivierte Methode innermathematisch. Im Einzelfall ist der Verlauf dieser äquivalent zur Konstruktion eines Spannbaums minimalen Gewichts in einem festgeschriebenen gewichteten Graph. Dieser Spannbaum lässt sich biologisch wiederum als Netzwerk kürzester genetischer Distanz interpretieren. Tropische Hyperflächen sind zentrale Objekte der tropischen Geometrie, eines eigens für sich aktiven Forschungsgebiets mit Anknüpfungspunkten zur polyedrischen, diskreten und algebraischen Geometrie. Diese Hyperflächen enthalten die betreffenden minimalen Spannbäume in ihrem eindimensionalen Skelett. Wir zeigen, dass der Parameterbereich dieser minimalen Spannbäume durch eine Sammlung polyedrischer Kegel gegeben ist. Für ausgewählte, kleine Bespiele gelingt es, eine explizite Darstellung für jeden einzelnen Parameterkegel zu berechnen. Dennoch stößt man dabei schnell auf unüberwindbare Komplexitätsschranken. Der Rest dieser Arbeit beschäftigt sich mit einer Thematik, die jenseits dieser Komplexitätsschranken liegt. Zwar mag es für eine implizit gegebene Zellzerlegung mit den aktuellen Methoden unmöglich sein, für jede einzelne Zelle eine explizite geometrische Beschreibung zu errechnen, jedoch kann durchaus eine Abzählung der Zellen erfolgen. Wir präsentieren eine rein kombinatorische Methode zur Abzählung der Kammern eines reellen Hyperebenenarrangements, die wesentlich auf der Ausnutzung kombinatorischer Symmetrie fußt. Mit dieser Methode war es uns möglich, die zuvor unbekannte Kammeranzahl des neunten Resonanzarrangements zu bestimmen, das durch 511 Hyperebenen im R^9 gegeben ist.

The thesis studies temporal graph problems and multistage problems. Since these problems typically are computationally hard, the focus is on developing fast exact (FPT-)algorithms. Temporal graph problems. A temporal graph is a graph whose edge set changes over time. Here, an edge at a specific time step is called time-edge. One of our main contributions is the introduction of a set of parameters tailored for temporal graph problems. We focus mainly on four problems on temporal graphs. Minimizing Reachability by Delaying. Given a temporal graph, a set of source vertices, and three integers k, r, and δ, the problem Minimizing Temporal Reachability by Delaying asks whether we can delay at most k time-edges by δ time steps (i.e., moving the edges δ time steps into the future) such that the sources can reach at most r vertices via temporal paths (i.e., paths using edges appearing in non-decreasing time-order). Our main contribution here is an algorithm running in O(r!k|G|) time, where |G| is the size of the temporal graph. This stands in contrast to the W[1]-hardness when parameterized by r for the problem of deleting instead of delaying time-edges. Restless Temporal Paths. A restless temporal path is a temporal path that can stay only a bounded amount of time at one vertex. Our main contribution here is a randomized algorithm to find a length-at-most-k restless temporal path from vertex s to vertex z in 4^ℓ |G|^O(1) time, where ℓ is the difference between k and the length of the shortest temporal path from s to z. Moreover, we show that finding these restless temporal paths is fixed-parameter tractable when parameterized by the timed feedback vertex number (that is, a temporal version of the classical feedback vertex number introduced in this thesis). This stands in contrast to the W[1]-hardness when parameterized by the feedback vertex number of the underlying graph. Temporal Separation. A temporal separator is a vertex set that intersects the vertices of all temporal paths between two distinguished vertices. We contribute two algorithms to find minimum temporal separators. The first algorithm runs in ω^ω |G|^O(1) time, where ω is the temporal core size—another parameter for temporal graphs introduced here. The second algorithm runs in 4^x |G|^O(1) time, where x is the timed feedback vertex number. This stands in contrast to the W[1]-hardness when parameterized by the feedback vertex number of the underlying graph. Temporal Matching. A δ-temporal matching in a temporal graph is a set of time-edges such that two distinct time-edges either do not share an endpoint or they are at least δ time steps apart. We present two algorithms to find δ-temporal matchings of size k. The first algorithm runs in O((2k − 1)^k |G|) time. Previously, only the fixed-parameter tractability for k + δ was known due to kernelization. The second algorithm runs in δ^O(ν) |G| time, where ν is the δ-vertex cover number—another new parameter we introduce here. Multistage problems. Many problems need not only be solved once but repeatedly, under changing conditions. This setting is addressed by the “multistage” view on computational problems, where the input contains a sequence of instances of a computational problem, and we are asked to find a sequence of solutions (one for each instance) under (dis)similarity constraints. We study two different variants. First, we study a “diverse multistage” variant, where consecutive solutions shall differ by at least ℓ elements, e.g., for reasons of fairness or wear minimization. We introduce a general framework allowing to prove that several diverse multistage problems are fixed-parameter tractable when parameterized by ℓ, namely Perfect Matching, s-t Path, and Plurality Voting. Second, we study Multistage Vertex Cover—a (non-diverse) “multistage” variant of Vertex Cover where we are given a sequence of instances of Vertex Cover, all instances asking for a vertex cover of size at most k. In contrast to the diverse multistage variant, consecutive vertex covers shall differ by at most ℓ vertices. In general, this multistage variant is motivated by scenarios where the adaptation of the current solution generates reconfiguration costs which shall not exceed ℓ. We show that Multistage Vertex Cover parameterized by k is W[1]-hard, already when ℓ = 2., Die Arbeit untersucht temporale Graphenprobleme und mehrstufige Probleme. Da diese Probleme typischerweise berechnungsschwer sind, liegt der Schwerpunkt auf der Entwicklung schneller, exakter (FPT-)Algorithmen. Temporale Graphenprobleme. Ein temporaler Graph ist ein Graph, dessen Kantenmenge sich im Laufe der Zeit verändert. Dabei wird eine Kante zu einem bestimmten Zeitpunkt als Zeitkante bezeichnet. Einer der wichtigsten Beiträge dieser Arbeit ist die Einführung einer Reihe von Parametern für temporale Graphenprobleme. Wir konzentrieren uns hauptsächlich auf vier temporale Graphenprobleme. Minimierung der Erreichbarkeit durch Verzögern. Gegeben ein temporaler Graph, eine Menge von Quellknoten und drei natürliche Zahlen k, r und δ, so fragt das Problem Minimierung der temporalen Erreichbarkeit durch Verzögern, ob wir höchstens k Zeitkanten um δ verzögern (d. h. die Zeitkante um δ Zeitschritte in die Zukunft verschieben) können, so dass die Quellen höchstens r Knoten über temporale Pfade erreichen können (d. h. Pfade mit Kanten, die in nicht abnehmender zeitlicher Reihenfolge auftreten). Hier ist unser Hauptbeitrag ein Algorithmus mit einer Laufzeit von O(r!k|G|), wobei |G| die Größe des temporalen Graphen ist. Dies steht im Gegensatz zu der W[1]-Schwere mit Parameter r, wenn wir Zeitkanten löschen statt verzögern. Rastlose temporale Pfade. Ein rastloser temporaler Pfad ist ein temporaler Pfad, der nur eine begrenzte Zeit an einem Knoten verweilen kann. Unser Hauptbeitrag ist ein randomisierter Algorithmus zum Finden eines rastlosen temporalen Pfades der Länge höchstens k von einem Knoten s zu einem Knoten z mit einer Laufzeit von 4^ℓ |G|^O(1) , wobei ℓ die Differenz zwischen k und der Länge eines kürzesten temporalen Pfades von s nach z ist. Außerdem zeigen wir, dass das Finden dieser rastlosen temporalen Pfade in FPT liegt, wenn das Problem mit der temporalen kreiskritischen Knotenzahl (das ist eine temporale Version der klassischen kreiskritischen Knotenzahl, die in dieser Arbeit eingeführt wird) parametrisiert wird. Dies steht im Gegensatz zu der W[1]-Schwere, wenn das Problem mit der kreiskritischen Knotenzahl des zugrundeliegenden Graphen parametrisiert wird. Temporale Trennung. Ein temporaler Trenner ist eine Knotenmenge, die die die Knotenmenge aller zeitlichen Pfade zwischen zwei bestimmten Knoten schneidet. Wir präsentieren zwei Algorithmen, um minimale temporale Trenner zu finden. Der erste Algorithmus hat eine Laufzeit von ω^ω |G|^O(1) , wobei ω die temporale Kerngröße ist – ein weiterer hier eingeführter Parameter für temporale Graphen. Der zweite Algorithmus hat eine Laufzeit von 4^x |G|^O(1) , wobei x die temporale kreiskritische Knotenzahl ist. Dies steht im Gegensatz zur der W[1]-Schwere, wenn das Problem mit der kreiskritischen Knotenzahl des zugrundeliegenden Graphen parametrisiert wird. Temporale Paarung. Ein δ-temporale Paarung in einem temporalen Graphen ist eine Menge von Zeitkanten, in der zwei unterschiedliche Zeitkanten entweder keinen gemeinsamen Endpunkt haben oder mindestens δ Zeitschritte voneinander entfernt sind. Wir entwickeln zwei Algorithmen, um δ-temporale Paarungen der Größe k zu finden. Der erste Algorithmus hat eine Laufzeit von O((2k − 1)^k |G|). Bislang war nur bekannt, dass dieses Problem in FPT liegt, wenn es mit k + δ parametrisiert wird. Der zweite Algorithmus hat eine Laufzeit von δ^O(ν) |G|, wobei ν die δ-Knotenüberdeckungszahl ist – ein weiterer neuer Parameter, der hier eingeführt wird. Mehrstufige Probleme. Viele Probleme müssen nicht nur einmal gelöst werden, sondern öfter und unter wechselnden Bedingungen. Dieser Umstand wird durch die „mehrstufige“ Betrachtung von Problemen adressiert, wobei die Eingabe eine Sequenz von Instanzen eines Problems enthält und wir nach einer Sequenz von Lösungen (für jede Instanz eine) unter (Un-)Ähnlichkeitsbeschränkungen suchen. Wir untersuchen zwei verschiedene Varianten. Erstens untersuchen wir eine „diverse mehrstufige“ Variante, bei der sich aufeinanderfolgende Lösungen um mindestens ℓ Elemente unterscheiden, z. B. aus Gründen der Gerechtigkeit oder der Verschleißminimierung. Wir führen ein allgemeines Werkzeug ein, welches erlaubt zu beweisen, dass mehrere diverse mehrstufige Probleme in FPT liegen, wenn sie mit ℓ parametrisiert werden. Wir wenden das Werkzeug für die Probleme Perfekte Paarung, s-t Pfad und Pluralitätsabstimmung an. Zweitens untersuchen wir die Mehrstufige Knotenüberdeckung – eine (nicht-diverse) „mehrstufige“ Variante von der Knotenüberdeckung, wobei alle Instanzen nach einer Knotenüberdeckung der Größe höchstens k fragen. Im Gegensatz zu der diversen mehrstufigen Variante dürfen aufeinanderfolgende Knotenüberdeckungen sich um höchstens ℓ Knoten unterscheiden. Im Allgemeinen ist diese mehrstufige Variante motiviert durch Szenarien, in denen die Anpassung der aktuellen Lösung Rekonfigurationskosten verursacht, die ℓ nicht überschreiten dürfen. Wir zeigen, dass Mehrstufige Knotenüberdeckung W[1]-schwer ist, wenn es mit k parametrisiert wird, selbst wenn ℓ = 2 gilt.

The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. In the past 10 years, there have been significant advances concerning approximation and complexity of the SPG. However, the state of the art in (practical) exact solution of the SPG has remained largely unchallenged for almost 20 years. While the DIMACS Challenge 2014 and the PACE Challenge 2018 brought renewed interest into Steiner tree problems, even the best new SPG solvers cannot match the state of the art on the vast majority of benchmark instances. The following article seeks to advance exact SPG solution once again. The article is based on a combination of three concepts: Implications, conflicts, and reductions. As a result, various new SPG techniques are conceived. Notably, several of the resulting techniques are (provably) stronger than well-known methods from the literature that are used in exact SPG algorithms. Finally, by integrating the new methods into a branch-and-cut framework, we obtain an exact SPG solver that is not only competitive with, but even outperforms the current state of the art on an extensive collection of benchmark sets. Furthermore, we can solve several instances for the first time to optimality.

The current pandemic is a great challenge for several research areas. In addition to virology research, mathematical models and simulations can be a valuable contribution to the understanding of the dynamics of the pandemic and can give recommendations to both physicians and politicians. In this paper we give an overview about mathematical models to describe the pandemic by differential equations. As a matter of principle the historic origin of the epidemic growth models will be remembered. Moreover we discuss models for the actual pandemic of 2020/2021. This will be done based on actual data of people infected with COVID-19 from the European Centre for Disease Prevention and Control (ECDC), input parameters of mathematical models will be determined and applied. These parameters will be estimated for the UK, Italy, Spain, and Germany and used in a SIR-type model. As a basis for the model’s calibration, the initial exponential growth phase of the COVID-19 pandemic in the named countries is used. Strategies for the commencing and ending of social and economic shutdown measures are discussed. To respect heterogeneity of the people density in the different federal states of Germany diffusion effects are considered.

We study optimal portfolio decisions for a retail investor that faces a strictly positive transaction cost in a classical Black‐Scholes market. We provide a construction of optimal trading strategies and characterize the value function as the unique viscosity solution of the associated quasi‐variational inequalities. Moreover, we numerically investigate the optimal trading regions for a variety of real‐world cost structures faced by retail investors. We find that the cost structure has a strong effect on the qualitative shape of the no‐trading region and optimal strategies.

A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the cut. A famous theorem of Lucchesi and Younger states that in every finite digraph the least size of an edge set meeting every dicut equals the maximum number of disjoint dicuts in that digraph. In this first paper out of a series of two papers, we conjecture a version of this theorem using a more structural description of this min‐max property for finite dicuts in infinite digraphs. We show that this conjecture can be reduced to countable digraphs where the underlying undirected graph is 2‐connected, and we prove several special cases of the conjecture.

We consider a nonlinear Dirichlet problem driven by the (p, q)-Laplacian and with a reaction having the combined effects of a singular term and of a parametric (p−1)-superlinear perturbation. We prove a bifurcation-type result describing the changes in the set of positive solutions as the parameter λ>0 varies. Moreover, we prove the existence of a minimal positive solution u∗λ and study the monotonicity and continuity properties of the map λ→u∗λ.

Let G be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a branching B is popular if B does not lose a head-to-head election (where nodes cast votes) against any branching. Such popular branchings have a natural application in liquid democracy. The popular branching problem is to decide if G admits a popular branching or not. We give a characterization of popular branchings in terms of dual certificates and use this characterization to design an efficient combinatorial algorithm for the popular branching problem. When preferences are weak rankings, we use our characterization to formulate the popular branching polytope in the original space and also show that our algorithm can be modified to compute a branching with least unpopularity margin. When preferences are strict rankings, we show that “approximately popular” branchings always exist.

We analyze the influence of an external sound source in a network of FitzHugh-Nagumo oscillators with empirical structural connectivity measured in healthy human subjects. We report synchronization patterns, induced by the frequency of the sound source. We show that the level of synchrony can be enhanced by choosing the frequency of the sound source and its amplitude as control parameters for synchronization patterns. We discuss a minimum model elucidating the modalities of the influence of music on the human brain., 6 Figures

Semitoric systems are a special class of completely integrable systems with two degrees of freedom that have been symplectically classified by Pelayo and Vũ Ngọc about a decade ago in terms of five symplectic invariants. If a semitoric system has several focus–focus singularities, then some of these invariants have multiple components, one for each focus–focus singularity. Their computation is not at all evident, especially in multi-parameter families. In this paper, we consider a four-parameter family of semitoric systems with two focus–focus singularities. In particular, apart from the polygon invariant, we compute the so-called height invariant. Moreover, we show that the two components of this invariant encode the symmetries of the system in an intricate way.

International audience; This special issue contains five articles which are based on extended abstracts presented at the 35th Symposium on Theoretical Aspects of Computer Science (STACS). The conference was held at the Technical University of Berlin from March 13 to March 16, 2019. The extended abstracts were chosen among the top papers of those which were selected for presentation in a highly competitive peer-review process (after which only 54 papers out of 260 submissions were accepted, putting it among the most competitive conferences in Theoretical Computer Science). Compared with the original conference papers, the articles have been extended with a description of the context, full proofs, and additional results. They underwent a rigorous reviewing process, following the TOCS journal standards, completely independent from the selection process of STACS 2019. The topics of the chosen papers cover various areas of Theoretical Computer Science, that is, algorithmic graph theory, automata theory, linear dynamical systems, parameterized complexity analysis, and distributed algorithms. In what follows, we briefly describe the contributions of the papers, ordered alphabetically by author names. Significantly extending the results of the conference version, the article "First-Order Orbit Queries" by Shaull Almagor, Joel Quaknine, and James Worrell studies fundamental reachability questions, so-called orbit problems: Here, for example, we are given a square matrix A of dimension d over the rationals and two semialgebraic

Image and data processing have become increasingly important over recent years. In particular, robust distance measures and transformation methods on large and perturbed data sets are of growing interest. These tasks become even more challenging if the measurement locations are distributed on some manifold or if the data itself has a manifold structure. In this thesis, we start by examining a time discrete manifold-valued morphing model together with a time continuous counterpart which includes a variational inequality and is inspired by the classical metamorphosis approach. For both models, existence of minimizers is shown under the assumption that the data lies in a finite-dimensional Hadamard manifold. Further, we prove Mosco convergence of the time discrete model to the time continuous one. Then, we propose to use the real-valued version of this model as variational regularizer for inverse problems if some template image is available. As this incorporates additional information into the reconstruction process, such an approach is particularly useful if the data is sparse. In cases where an even stronger regularization is necessary, we propose to use a more restrictive flow of diffeomorphism based model instead. Additionally, increased robustness to intensity differences between template and ground-truth is achieved by using a distance measure based on normalized cross-correlation. These modifications enable us to obtain promising reconstructions for computed tomography with a very sparse number of angles. For both models existence, stability and convergence for vanishing noise are proven. Besides metamorphosis and flow of diffeomorphism, we are interested in optimal transport between images. More precisely, we investigate Sinkhorn divergences, which interpolate between optimal transport and discrepancies. Here, we focus on the behavior of the corresponding optimal dual potentials and establish a relation between their limits as the regularization parameter goes to infinity and the optimal potential of the associated discrepancy. Additionally, we compare these different distance measures for a process called dithering. Finally, we investigate the approximation of probability measures on compact metric spaces and in particular on Riemannian manifolds by measures supported on Lipschitz curves. For this purpose, the approximation quality is assessed in terms of discrepancies as these do not suffer from the so-called curse of dimensionality. % Potential applications are 3D printing and magnetic resonance imaging. While we also investigate the general case via the traveling salesman approach, a strong focus lies on the push-forward of the Lebesgue measure on the unit interval by Lipschitz continuous curves. Here, we utilize a result on the quadrature error achievable by integration with respect to a measure that exactly integrates all eigenfunctions of the Laplace--Beltrami operator with eigenvalues smaller than a fixed number. In particular, this enables us to provide optimal approximation rates in terms of the curve's length and Lipschitz constant for measures fulfilling smoothness requirements. All results established in this thesis are illustrated by numerical proof-of-concept examples and comparisons. These include real-world data experiments in particular for our flow of diffeomorphism based reconstruction model. For the necessary discrepancy evaluations, recent fast Fourier transform techniques on certain manifolds are exploited., Bild- und Datenverarbeitung haben in den letzten Jahren zunehmend an Bedeutung gewonnen. Dabei haben sich insbesondere robuste Abstandsmaße und Transformationsmethoden für große und gestörte Datensätze als wichtig erwiesen. Diese Aufgaben werden noch komplizierter, wenn die Messpunkte auf einer Mannigfaltigkeit verteilt sind oder wenn die Daten selbst eine Mannigfaltigkeitsstruktur besitzen. In dieser Arbeit untersuchen wir zunächst ein zeitdiskretes Morphing-Modell für mannigfaltigkeitswertige Bilder zusammen mit einem zeitkontinuierlichen Pendant, welches auf einer Variationsungleichung basiert und vom klassischen Metamorphosis Modell inspiriert ist. Für beide Ansätze wird die Existenz von Minimierern unter der Annahme gezeigt, dass die Daten in einer endlichdimensionalen Hadamard-Mannigfaltigkeit liegen. Außerdem beweisen wir die Mosco-Konvergenz des zeitdiskreten Modells gegen das zeitkontinuierliche Modell. Falls ein geeignetes Referenzbild verfügbar ist, wollen wir die reellwertige Version dieses Modells als Regularisierer für das Lösen inverser Probleme verwenden. Da hierdurch zusätzliche Information in den Rekonstruktionsprozess eingebunden wird, ist ein solcher Ansatz insbesondere dann nützlich, wenn die Daten unvollständig sind. Ist eine noch stärkere Regularisierung erforderlich, verwenden wir stattdessen ein restriktiveres und auf dem Fluss des Diffeomorphismus basierendes Modell. Zusätzlich kann die Robustheit gegenüber Intensitätsunterschieden zwischen Referenzbild und dem unbekannten Signal durch die Verwendung eines auf der normalisierten Kreuzkorrelation basierenden Abstandsmaßes verbessert werden. Diese Modifikationen ermöglichen es uns, vielversprechende Rekonstruktionen für Computertomografie mit einer sehr geringen Anzahl von Winkeln zu erhalten. Für beide Modelle werden Existenz, Stabilität und Konvergenz für verschwindendes Rauschen gezeigt. Neben dem Metamorphosis und dem Fluss des Diffeomorphismus Modell sind wir auch an optimalem Transport zwischen Bildern interessiert. Genauer gesagt untersuchen wir Sinkhorn-Divergenzen, die zwischen optimalem Transport und Diskrepanzen interpolieren. In dieser Arbeit konzentrieren wir uns auf das Verhalten der entsprechenden optimalen dualen Potentiale und stellen eine Beziehung zwischen ihren Grenzwerten für wachsende Regularisierungsparameter und dem optimalen Potential der zugehörigen Diskrepanz her. Zusätzlich vergleichen wir die vorgestellten Abstandsmaße für einen Prozess namens "Dithering". Schließlich untersuchen wir die Approximation von Wahrscheinlichkeitsmaßen auf kompakten metrischen Räumen und insbesondere auf Riemannschen Mannigfaltigkeiten durch Maße, deren Träger eine lipschitzstetige Kurve ist. Zu diesem Zweck wird die Approximationsqualität anhand von Diskrepanzen beurteilt, da diese nicht vom sogenannten Fluch der Dimension betroffen sind. Während wir auch den allgemeinen Fall über das Problem des Handlungsreisenden untersuchen, liegt der Fokus auf Bildmaßen vom Lebesgue-Maß auf dem Einheitsintervall bezüglich lipschitzstetiger Kurven. Hierbei verwenden wir ein Ergebnis zum Quadraturfehler bezüglich der Integration mit Maßen, welche Eigenfunktionen des Laplace--Beltrami Operators mit Eigenwerten kleiner einer festen Zahl exakt integrieren. Insbesondere können wir dadurch optimale Approximationsraten in Abhängigkeit der Kurvenlänge und der Lipschitz-Konstante für Maße zeigen, die zusätzliche Glattheitseigenschaften erfüllen. Alle in dieser Arbeit erzielten Ergebnisse werden durch numerische Konzeptnachweise und Vergleiche sowie Experimente mit realen Daten insbesondere für unser auf dem Fluss des Diffeomorphismus basierenden Rekonstruktionsmodell veranschaulicht. Für die notwendigen Diskrepanzberechnungen werden vor kurzem entwickelte schnelle Fourier-Transformationstechniken auf ausgewählten Mannigfaltigkeiten genutzt.

Nowadays, transmission system operators of energy networks (TSO) have to enable secure energy supply even under challenging transport situations and increasing demand. Hence, they seek a stable network control and regularly expand the capacity of their networks. The challenging questions arise of how to obtain safe network operations for fixed network infrastructure and how to extend the network capacity at minimum cost. In this thesis, we formulate these two questions as mathematical optimization problems and present solution approaches that scale to real-world instances of size and complexity encountered in practice. Model formulations of both problems are located in the field of Mixed-Integer Nonlinear Programming (MINLP). However, global state-of-the-art MINLP solvers are not mature enough to solve or even find primal solutions on large-scale real-world instances since the resulting degree of nonconvexity and nonlinearity pose principal difficulties. For this reason, we develop novel model formulations and optimization algorithms that significantly improve the performance of the solver SCIP. The first part of the thesis focuses on the optimization of stationary network expansions by building new pipelines in parallel to existing ones, so-called looping. Based upon a model reduction approach for multiple loops, we introduce new models for the discrete and split-pipe looping paradigm and compare them with existing models in the literature, both theoretically and empirically. It turns out that our novel split-pipe model performs best in several respects: running time, number of instances solved, and cost savings by up to 7000% over the discrete models. To further improve the performance, we analytically calculate the convex envelope of the nonconvex, nonlinear constraint function f(x,y) = y sgn(x) |x|^a, which models the physical effect of the expansion. In this way, we considerably tighten the convex relaxation of the network expansion problem. The resulting implementation significantly reduces the average solving time by up to 58% on difficult instances. The second part of the thesis deals with the optimization of operations in transient large-scale networks. The problem consists of making day-ahead control decisions that enable feasible energy transport. To this end, we propose a specially-tailored solution approach. First, we aggregate network structures, which TSOs typically consider as of minor importance for the decision-making process. Then, we apply model reformulations that exploit the disjunctive nature of certain network structures and strengthen the linear relaxation. Finally, we present a primal heuristic based on time decomposition. The heuristic solves MINLP sub-models to acquire transport decisions for single time steps. We equip the heuristic with a mechanism that enables moving forward and backward on the time scale to compensate for possibly disadvantageous decisions taken at earlier stages. An extensive computational study shows that our approach reliably generates solutions for 96% to 100% of the instances for three different large-scale real-world networks. Parts of the developed methods are already in use by our industrial cooperation partner Open Grid Europe GmbH to facilitate the respective decision-making processes., Heutzutage m��ssen Betreiber von Energienetzen auch unter schwierigen Transportsituationen und steigender Bedarfsnachfrage die Energieversorgung sicherstellen. Sehr gro��e Herausforderungen bestehen dabei zum einen in der Gew��hrleistung des zul��ssigen Energietransports innerhalb einer gegebenen Netz-Infrastruktur und zum anderen in der kosteng��nstigen Kapazit��ts-Erweiterung durch Netzausbauten. In der vorliegenden Arbeit formulieren wir diese beiden Aufgaben als mathematische Optimierungsprobleme und entwickeln L��sungsans��tze f��r praxisrelevante Instanzen von bedeutender Gr����e und Komplexit��t. Die resultierenden Modellformulierungen geh��ren zur Klasse der gemischt-ganzzahligen nichtlinearen Programmierung (MINLP). Allerdings sind globale MINLP L��ser meist nicht in der Lage, gro��e praxisbezogene Probleminstanzen zu l��sen bzw. Primall��sungen zu finden, da modellinh��rente Nichtkonvexit��ten und Nichtlinearit��ten signifikante Schwierigkeiten im L��sungsprozess darstellen. In dieser Arbeit entwickeln wir Modellformulierungen und Optimierungsalgorithmen, die diese Schwierigkeiten adressieren und die Performanz des L��sers SCIP deutlich verbessert. Der erste Teil dieser Arbeit befasst sich mit der Optimierung von station��ren Netzerweiterungen, bei denen Rohre parallel zu existierenden Rohren gebaut werden, sogenannte Loops. Basierend auf einem Modellreduktionsansatz f��r kosteneffiziente mehrfache Loops, f��hren wir neue Modellformulierungen f��r das diskrete und split-pipe Paradigma ein und vergleichen sie theoretisch und experimentell mit Modellen aus der Literatur. Es stellt sich heraus, dass unser neues split-pipe Modell die deutlich beste Performanz aufweist und insgesamt zu Kosteneinsparungen von bis zu 7000% gegen��ber den diskreten Modellen f��hrt. Um die Performanz weiter zu verbessern, entwickeln wir die st��rkere konvexe Relaxierung des station��ren Ausbauproblems. Dazu berechnen wir f��r die konvexe Einh��llende der nichtkonvexen und nichtlinearen Bedingung f(x,y) = y sgn(x) |x|^a, welche die physikalische Wirkung des Ausbaus darstellt, eine algebraische L��sung in geschlossener Form. Die resultierende Implementierung reduziert die durchschnittliche Rechenzeit um bis zu 58% f��r schwierige Instanzen. Der zweite Teil der Arbeit besch��ftigt sich mit der Optimierung des Betriebs von transienten gro��en Energienetzen. Ziel ist es, Kontrollentscheidungen zu treffen, die einen zul��ssigen Energietransport erm��glichen. Zu diesem Zweck entwickeln wir einen mehrstufigen L��sungsansatz. Zun��chst aggregieren wir Teile des Netzes, die typischerweise f��r die Entscheidungsfindung von Netzbetreibern als weniger wichtig angesehen werden. Dann wenden wir Modell-Reformulierungen an, die den disjunkten Charakter einiger Netzstrukturen ausnutzen und die lineare Relaxierung des Problems st��rken. Schlie��lich pr��sentieren wir eine auf Zeit-Dekomposition basierende Primalheuristik. Hier werden durch das L��sen von MINLP Submodellen Transportentscheidungen f��r die einzelnen Zeitschritte generiert. Dabei statten wir die Heuristik mit einem Mechanismus aus, der es erm��glicht, auf der Zeitskala vor und zur��ck zu gehen, um unvorteilhafte Entscheidungen, die in fr��heren Zeitschritten getroffen wurden, zu dekompensieren. Umfangreiche Rechenexperimente zeigen, dass unser Ansatz zuverl��ssig Primall��sungen f��r insgesamt 96% bis 100% aller Instanzen f��r drei verschiedene gro��e reale Netzwerke findet. Teile der in dieser Arbeit entwickelten Methoden sind bereits bei unserem industriellen Projektpartner Open Grid Europe GmbH im Einsatz.

We introduce group field theory networks as a generalization of spin networks and of (symmetric) random tensor networks and provide a statistical computation of the R\'enyi entropy for a bipartite network state using the partition function of a simple interacting group field theory. The expectation value of the entanglement entropy is calculated by an expansion into stranded Feynman graphs and is shown to be captured by a Ryu- Takayanagi formula. For a simple interacting group field theory, we can prove the linear corrections, given by a polynomial perturbation of the Gaussian measure, to be negligible for a broad class of networks., Comment: 40 pages, 13 figures

Certain approximation techniques for the numerical solution of partial differential equations result in linear algebraic systems where the coefficient matrix is nonsymmetric, nonnormal and ill-conditioned. This is the case for the finite difference discretization of the convection-diffusion equation posed on a Shishkin mesh treated in this work. We present a convergence analysis of the (algebraic) multiplicative Schwarz method when it is used to solve linear systems arising from both the upwind and central finite difference discretization approaches to such problems. For one and two dimensional problems, we show that the iteration matrix of the method has low-rank, which allows us to bound its infinity-norm. These bounds lead to quantitative error bounds for the iterates of the method that are valid from the first step of the iteration process. For problems in one-dimension, we prove rapid convergence of the method for all parameter choices of the problem when the upwind discretization approach is used, while convergence can only be proven for certain parameter choices for the central difference approach. Only the upwind discretization is considered in the case of two-dimensional problems. Furthermore, we consider the method as a preconditioner to GMRES and prove the convergence of the preconditioned method in a small number of steps when the local subdomain problems are solved exactly. Numerical experiments show that, for problems in two-dimensions, the number of iterations either stays the same or decreases for the case of inexact local solves, achieving a speed up in computational time. We continue by generalizing our convergence results to the case where the coefficient matrix of the linear system possess a special block structure that arises, for example, when a partial differential equation is posed and discretized on a domain that consists of two subdomains that overlap. Our analysis does not assume that the system matrices resulting from the discretization process are symmetric (positive definite) or posses the M- or H-matrix property. Instead, our results are obtained by generalizing the theory of diagonal dominant matrices from the scalar to the block case. Based on this generalization we present bounds on the norms of the inverses of general block tridiagonal matrices and derive a variant of the Gershgorin Circle Theorem that provides eigenvalue inclusion regions in the complex plane that are potentially tighter than the usual sets derived from the classical definition., Bestimmte Approximationstechniken für die numerische Lösung partieller Differentialgleichungen führen zu linearen algebraischen Systemen, bei denen die Koeffizientenmatrix nicht symmetrisch, nicht normal und schlecht konditioniert ist. Dies ist der Fall zum Beispiel bei der Diskretisierung der Konvektions-Diffusions-Gleichung, die in dieser Arbeit auf einem Shishkin-gitter aufgestellt wurde. Wir stellen eine Konvergenzanalyse der (algebraischen) multiplikativen Schwarz-Methode vor, wenn sie zur Lösung linearer Systeme verwendet wird, die sich sowohl aus dem Upwind als auch aus dem zentralen Finite-Differenz-Diskretisierungsansatz für solche Probleme ergeben. Für ein- und zweidimensionale Probleme zeigen wir, dass die Iterationsmatrix der Methode einen niedrigen Rang hat, was uns erlaubt, ihre infinity-Norm abzuschätzen. Diese Schranken führen zu quantitativen Fehlerschranke für die Iterationen der Methode, die ab dem ersten Schritt des Iterationsprozesses gültig sind. Bei eindimensionalen Problemen beweisen wir eine schnelle Konvergenz der Methode für alle Parameterwahlen des Problems, wenn der Upwind-Diskretisierungsansatz verwendet wird, während die Konvergenz nur für bestimmte Parameterwahlen für den zentralen Differenzansatz nachgewiesen werden kann. Bei zweidimensionalen Problemen wird nur die Upwind-Diskretisierung berücksichtigt. Darüber hinaus betrachten wir die Methode als Vorkonditionierer von GMRES und weisen die Konvergenz der vorkonditionierten Methode in wenigen Schritten nach, wenn die lokalen Teilbereichsprobleme exakt gelöst werden. Numerische Experimente zeigen, dass bei zweidimensionalen Problemen die Anzahl der Iterationen entweder gleich bleibt oder bei ungenauen lokalen Lösungen abnimmt, wodurch eine Beschleunigung der Rechenzeit erreicht wird. Wir fahren fort, indem wir unsere Konvergenzergebnisse auf den Fall verallgemeinern, dass die Koeffizientenmatrix des linearen Systems eine spezielle Blockstruktur besitzt, die sich z.B. ergibt, wenn eine partielle Differentialgleichung auf einem Gebiet gestellt und diskretisiert wird, die aus zwei Untergebiete besteht, die sich überlappen. Unsere Analyse geht nicht davon aus, dass die aus dem Diskretisierungsprozess resultierenden Systemmatrizen symmetrisch (positiv definit) sind oder die Eigenschaft der M- oder H-Matrix besitzen. Stattdessen erhalten wir unsere Ergebnisse durch Verallgemeinerung der Theorie der diagonaldominanten Matrizen vom skalaren zum Blockfall. Basierend auf dieser Verallgemeinerung beschränken wir die Norm der Inversen von allgemeinen Blocktridiagonalmatrizen und leiten eine Variante des Satz von Gershgorin her. Die Eigenwert-Einschlussbereiche in der komplexen Ebene liefert, die potenziell kleiner sind als die klassischen Gershgorin-Kreise.

In this thesis, we consider the class of high dimensional functions which contains functions which are defined in high-dimensional spaces but are known to be constant along some unknown manifolds. We study different reconstruction problems under additional assumptions. In the papers [54, 41, 56] (see Appendix A – C), we consider this problem in the context of compressed sensing and study the following problems. In Appendix A, [54], we assume that we aim to reconstruct a sparse and finite-valued vector. We present an approach that incorporates a finite values prior into basis pursuit, which is one classical reconstruction strategy in compressed sensing. In particular, we address unipolar binary and bipolar ternary sparse signals. We show that phase transition takes place earlier than using the classical basis pursuit approach and that, independently of the sparsity of the signal, at most N/2, respectively 3N/4, measurements are necessary to recover a unipolar binary, and a bipolar ternary signal uniquely. We further discuss robustness with respect to noisy measurements and generalizations to signals with entries in larger alphabets. In this work we consider Gaussian measurements. In Appendix B, [41], we concentrate on the recovery of sparse, (unipolar) binary signals through box-constrained basis pursuit. In contrast to the work in Appendix A we use biased measurement matrices, whose entries have a nonzero expected value. This enables us, using a probabilistic model, to provide conditions under which the recovery of both s-sparse and saturated binary signals is very likely. In fact, we also show that under the same conditions, the solution of the boxed-constrained basis pursuit program can be found using boxed-constrained least squares, which has some practical impact. This allows for example to establish stability without a-priori knowledge on the noise level. In Appendix C, [56], we also study the reconstruction of binary sparse signals from biased measurements. In contrast to the work in Appendix B, however, we consider biased partial random circulant instead of fully random measurements. We again show that the reconstruction via the least-squares strategy is as good as the reconstruction via the usually used program basis pursuit. We further show that we need as many measurements to recover an sparse signal as we need to recover a saturated signal. We further establish stability with respect to noisy measurements. Then, in [55],we study the approximation of generalized ridge functions, namely of functions which are constant along some submanifolds. We introduce the notion of linear-sleeve functions, whose function values only depend on the distance to some unknown linear subspace. We propose two effective algorithms to approximate linear-sleeve functions. We prove error bounds for both algorithms and provide an extensive numerical comparison of both. We further discuss an approach to apply these algorithms to capture general sleeve functions, which depend on the distance to some lower dimensional submanifold., In dieser Dissertation betrachten wir die Klasse von Funktionen, welche Funktionen enthält, die auf hochdimensionalen Räumen definiert aber konstant auf unbekannten Untermannigfaltigkeiten sind unter zusätzlichen Voraussetzungen untersuchen wir in diesem Zusammenhang unterschiedliche Rekonstruktionsprobleme. In den Veröffentlichungen [54, 41, 56] (siehe Appendix A – C) betrachten wir dieses Problem im Kontext des Compressed Sensings und untersuchen drei verschiedene Probleme. In [54] (siehe Appendix A), nehmen wir an, dass wir ein dünn besetztes Signal dessen Einträge aus einem endlichen Alphabet stammen rekonstruieren wollen. Wir präsentieren einen Ansatz zur Lösung des Problems, in welchem die Endlichkeit des Alphabets als Prior in die sogenannte l1-Minimierung, als Rekonstruktionsmethode, eingebaut wird. Die l1-Minimierung ist eine klassische Methode, die im Bereich des Compressed Sensing viel Anwendung findet. Insbesondere betrachten wir unipolare binäre und bipolar ternäre Signale. Wir zeigen, dass die sogenannte „Phase Transition“ früher stattfindet als bei der klassischen l1-Minimierung und dass, unabhängig von der dünnen Besetzung des Signals, N/2 beziehungsweise 3N/4 Messungen ausreichen, um ein unipolar binäres oder bipolar ternäres Signal eindeutig zu rekonstruieren. Darüber hinaus diskutieren wir die Robustheit des Algorithmus sowie Verallgemeinerungen auf Signale mit Einträgen aus größeren Alphabeten. In dieser Arbeit betrachten wir insbesondere Gauß-Messungen. In [41] (siehe Appendix B), konzentrieren wir uns auf die Rekonstruktion von dünn besetzen, (unipolar) binären Signalen mittels l1-Minimierungen unter sogenannten Box-Bedingungen, also der Bedingung, dass die Einträge des zu rekonstruierenden Signals in der Box [0, 1] liegen müssen. Im Gegensatz zu der Arbeit in Appendix A benutzen wir verschobene zufällige Messmatrizen, deren Einträge einen von Null verschieden Erwartungswert haben. Dies versetzt uns in die Lage, Bedingungen zu erarbeiten, unter denen die Rekonstruktion eines s-dünnen binären Signals genauso gut funktioniert, wie die Rekonstruktion eines (N-s)-dünnen, also unter Umständen dicht besetzten, binären Signals. Weiterhin zeigen wir sogar, dass unter denselben Bedingungen die Lösung der l1-Minimierung mit Box-Bedingungen genauso durch die Kleinste-Quadrate-Methode mit Box-Bedingungen gefunden werden kann. Das hat einige praktische Vorteile, da es uns beispielsweise erlaubt, Robustheit zu zeigen, ohne die Größenordnung der Störung vorher zu kennen. In [56] (siehe Appendix C), betrachten wir ebenso die Rekonstruktion von binären Signalen aus verschobenen zufälligen Messungen. Statt komplett randomisierter Matrizen betrachten wir nun randomisierte zyklische Matrizen. Dies ist für einige Anwendungen von Vorteil, da diese Matrizen unter anderem deutlich geringere Speicheranforderungen besitzen. Wir zeigen erneut, dass die Rekonstruktion mittels der Kleinste-Quadrate- Methode mit Box-Bedingungen genauso gut funktioniert wie die l1-Minimierung mit Box-Bedingungen. Darüber hinaus beweisen wir, dass man genauso viele Messungen benötigt, ein s-dünnes Signal zu rekonstruieren, wie ein (N -s)-dünnes (dicht besetztes) Signal. Weiterhin weisen wir Robustheit in Bezug auf gestörte Messungen nach. In [55] (siehe Appendix D) untersuchen wir die Approximation von verallgemeinerten Ridge Funktionen, genau genommen von Funktionen, die konstant entlang bestimmter Untermannigfaltigkeiten sind. Wir führen den Begriff der linearen-Sleeve Funktionen ein, deren Funktionswerte nur von der Distanz zu einem linearen Unterraum abhängen. Wir schlagen zwei effektive Algorithmen vor, um lineare-Sleeve Funktionen f (x) = g(dist(x, L)2) zu rekonstruieren. Weiterhin werden wir Fehlerschranken für beide Algorithmen beweisen und sie numerisch vergleichen. Am Ende werden wir noch eine Möglichkeit diskutieren, diese Ansätze auf noch allgemeinere Sleeve-Funktionen anzuwenden.

The thesis “Efficient Graph Exploration” studies the following three closely related problems, where collaborating mobile agents move in a graph and have to jointly perform a certain task. Chapter 2 “Space Efficient Graph Exploration” considers the problem of deterministically exploring an undirected and initially unknown graph with n vertices either by a single agent equipped with a set of pebbles or by a set of collaborating agents. The goal is to understand how the memory requirement decreases compared to the case of single agent exploration as the agent may mark vertices by dropping and retrieving distinguishable pebbles, or when multiple agents jointly explore the graph. It is shown that for a single agent with constant memory θ(log log n) pebbles are both necessary and sufficient for exploring any undirected graph with n vertices. The second main result is that θ(log log n) agents with constant memory each are necessary and sufficient for the same task. Thus collaborating agents are not more powerful than pebbles in this setting. Chapter 3 “Energy Efficient Tree Exploration” considers a model where an agent consumes energy proportional to the number of edges it traverses and every agent has a fixed energy budget B bounding the number of edges it can traverse. All agents start at the root of a tree and have no initial knowledge about its structure. The objective is to maximize the number of distinct vertices collectively visited by the given agents compared to an algorithm that has complete knowledge of the tree in advance. A 3-competitive algorithm for the problem is presented together with a lower bound of 2.17 on the competitive ratio of any online algorithm. In Chapter 4 “Energy Efficient Delivery”, the agents also consume energy proportional to the distance they travel, but different agents can have different rates of energy consumption. The task of the agents is to deliver a set of messages, which are specified as source-target pairs in an undirected weighted graph, while minimizing the total energy consumption for this task. The aim is to investigate how the agents benefit from collaborating on delivering the messages compared to the case that every message is only transported by a single agent. It is shown how an optimal solution to the delivery problem can be 2-approximated by a solution, where messages are only transported by a single agent. It is further proved that this is best possible for arbitrary number of messages and agent capacity, i.e., number of messages that can be transported at the same time., In der Dissertation „Efficient Graph Exploration“ werden verschiedene Modelle untersucht, in denen sich kooperierende mobile Agenten in einem Graphen bewegen um zusammen eine Aufgabe zu erledigen. In Kapitel 2 „Space Efficient Graph Exploration“ wird analysiert, wie ein Agent mit sogenannten Pebbles oder mehrere kooperierende Agenten deterministisch einen ungerichteten und anfangs unbekannten Graphen mit The thesis “Efficient Graph Exploration” studies the following three closely related problems, where collaborating mobile agents move in a graph and have to jointly perform a certain task. Chapter 2 “Space Efficient Graph Exploration” considers the problem of deterministically exploring an undirected and initially unknown graph with n vertices either by a single agent equipped with a set of pebbles or by a set of collaborating agents. The goal is to understand how the memory requirement decreases compared to the case of single agent exploration as the agent may mark vertices by dropping and retrieving distinguishable pebbles, or when multiple agents jointly explore the graph. It is shown that for a single agent with constant memory θ(log log n) pebbles are both necessary and sufficient for exploring any undirected graph with n vertices. The second main result is that θ(log log n) agents with constant memory each are necessary and sufficient for the same task. Thus collaborating agents are not more powerful than pebbles in this setting. Chapter 3 “Energy Efficient Tree Exploration” considers a model where an agent consumes energy proportional to the number of edges it traverses and every agent has a fixed energy budget B bounding the number of edges it can traverse. All agents start at the root of a tree and have no initial knowledge about its structure. The objective is to maximize the number of distinct vertices collectively visited by the given agents compared to an algorithm that has complete knowledge of the tree in advance. A 3-competitive algorithm for the problem is presented together with a lower bound of 2.17 on the competitive ratio of any online algorithm. In Chapter 4 “Energy Efficient Delivery”, the agents also consume energy proportional to the distance they travel, but different agents can have different rates of energy consumption. The task of the agents is to deliver a set of messages, which are specified as source-target pairs in an undirected weighted graph, while minimizing the total energy consumption for this task. The aim is to investigate how the agents benefit from collaborating on delivering the messages compared to the case that every message is only transported by a single agent. It is shown how an optimal solution to the delivery problem can be 2-approximated by a solution, where messages are only transported by a single agent. It is further proved that this is best possible for arbitrary number of messages and agent capacity, i.e., number of messages that can be transported at the same time. n Knoten explorieren können. Es wird gezeigt, dass für einen Agenten mit konstanter Speichergröße θ(log log n) Pebbles hinreichend und notwendig sind, um jeden Graphen mit n Knoten zu explorieren. Es wird außerdem bewiesen, dass für die gleiche Aufgabe θ(log log n) Agenten mit konstanter Speichergröße hinreichend und notwendig sind. Das heißt, in diesem Modell sind zusätzliche kooperierende Agenten nicht mächtiger als zusätzliche Pebbles. In Kapitel 3 „Energy Efficient Tree Exploration“ wird ein Modell betrachtet, in dem ein Agent Energie proportional zur Anzahl der traversierten Kanten verbraucht. Jeder Agent besitzt ein festes Energiebudget B und kann daher höchstens B Kanten traversieren. Anfangs befinden sich alle Agenten an der Wurzel eines Baumes und haben keinerlei Wissen über dessen Struktur. Das Ziel ist eine maximale Anzahl an Knoten mit den Agenten zu besuchen im Vergleich zu einem Algorithmus, der den kompletten Baum von Anfang an kennt. Es wird ein 3-kompetitiver Algorithmus für das Problem vorgestellt, sowie eine untere Schranke für die Competitive Ratio von 2.17 gezeigt. In Kapitel 4 „Energy Efficient Delivery“ wird ebenfalls ein Modell betrachtet, in dem Agenten Energie proportional zur Distanz, die sie im Graphen zurücklegen, verbrauchen. Allerdings kann sich in diesem Modell die Effizienz der Agenten, das heißt, deren Verbrauchsrate, unterscheiden. Die Aufgabe der Agenten ist eine Menge an Nachrichten jeweils von verschiedenen Startknoten zu verschiedenen Zielknoten in einem ungerichteten gewichteten Graphen zu transportieren und dabei die Gesamtmenge an verbrauchter Energie zu minimieren. Der Fokus in diesem Kapitel ist zu untersuchen, wie die Agenten davon profitieren können, zusammen zu wirken um eine Nachricht ans Ziel zu transportieren gegenüber dem Fall, dass jede Nachricht nur durch einen Agenten transportiert wird. Es wird gezeigt, wie sich eine optimale Lösung für das Problem in eine Lösung mit höchstens 2-fachen Kosten transformieren lässt, in der jede Nachricht nur von einem Agenten transportiert wird. Es stellt sich heraus, dass dies im Allgemeinen bestmöglich ist.

The computation of the homology groups of semialgebraic sets (given by Boolean formulas) remains one of the open challenges of computational semialgebraic geometry. Despite the search for an algorithm taking singly exponential time only on the number of variables, as of today, the existing algorithms are symbolic and doubly exponential. In this PhD thesis, we show how to obtain a numerical algorithm running in single exponential time with very high probability, which improves the state-of-the-art. To do so, we explain the underlying ideas, methods and techniques from numerical algebraic geometry, numerical complexity and topological data analysis that made this progress possible. We finish with a list of open problems and questions pointing to a possible future of the numerical computation of topological invariants. Additionally, in the appendices, we cover the topic of the expected number of real zeros of a random fewnomial system and we give an accessible account of the central theme in Spanish., Die Berechnung der Homologiegruppen von semialgebraischen Mengen (gegeben durch Boolesche Formeln) bleibt eine der offenen Herausforderungen der algorithmischen semialgebraischen Geometrie. Trotz der Suche nach einem Algorithmus mit einfach exponentieller Laufzeit in der Anzahl der Variablen, sind die nach heutigem Stand bekannten Algorithmen symbolisch und doppelt exponentiell. In dieser Doktorarbeit zeigen wir, wie man einen numerischen Algorithmus konstruiert, der mit großer Wahrscheinlichkeit einfach exponentiell ist und somit den Stand der Forschung verbessert. Dazu erklären wir die zugrundliegenden Ideen, Methoden und Techniken von numerischer algebraischen Geometrie, numerischer Komplexität und topologischer Datenanalyse, die dieser Fortschrift möglich machten. Wir enden mit einer Liste offener Probleme und Fragen, die auf eine mögliche Zukunft von Berechnung der topologischen Invarianten weisen. Außerdem behandeln wir im Anhang die erwartete Anzahl reeller Nullstellen eines zufälligen Systems polynomialer Gleichungen mit wenigen Termen und geben einen informellen Überblick über das Hauptthema auf Spanisch., El cálculo de los grupos de homología de conjuntos semialgebraicos (dados por fórmulas booleanas) es todavía uno de los mayores desafíos de la geometría semialgebraica computacional. Aunque se busca un algoritmo que tome a lo sumo tiempo simplemente exponencial en el número de variables, hasta el día de hoy todos los algoritmos existentes son simbólicos y doblemente exponenciales. En esta tesis doctoral, mostramos cómo se puede obtener un algoritmo numérico que tome tiempo simplemente exponencial con alta probabilidad, lo cual es una mejora del estado del arte. Para ello, explicamos las ideas, métodos y técnicas subyacentes procedentes de la geometría algebraica numérica, de la complejidad numérica y del análisis topológico de datos que han hecho posible este progreso. Terminamos con una lista de problemas y preguntas abiertas que indican un posible futuro de la computación numérica de invariantes topológicos. Además, en los apéndices, estudiamos el número esperado de ceros reales de un sistema oligonómico aleatorio y damos una visión informal del tema principal de esta tesis en castellano., Multzo semialjebraikoen (formula boolearrek emandakoen) homologia-taldeak kalkulatzeak jarraitzen du, oraindik ere, geometria semialjebraiko konputazionalaren erronka handienetako bat izaten. Bilatzen den algoritmoak aldagai kopuruan baino ez du hartzen denbora behin esponentziala; hala ere, gaur egun dauden algoritmo guztiak sinbolikoak eta bi aldiz esponentzialak dira. Doktorego-tesi honetan erakusten dugu nola lor daitekeen debora behin esponentzialean eta probabilitate handiarekin exekutatzen den zenbakizko algoritmo bat; hori teknikaren egoeraren hobekuntza da. Horretarako, zenbakizko geometria aljebraikoaren, zenbakizko konplexutasunaren eta datu-analisi topologikoaren azpian dauden eta aurrerapen hori posible egin duten ideia, metodo eta teknikak azaltzen ditugu. Problemen eta galdera irekien zerrenda batekin bukatzen dugu, zeinek inbariante topologikoen zenbakizko konputazioaren etorkizun posible bat adierazten baitute. Gainera, eranskinetan, ausazko sistema oligonomiko baten zero kopurua aztertzen dugu, eta tesi honen ikuspegi informala ematen dugu gaztelaniaz.

In this work, we study planar graphs with prescribed face areas. This field is inspired by cartograms. A 'cartogram' is a distorted map where the size of the regions are proportional to some statistical parameter such as the population, the total birth, the gross national product, or some other special property. As a mathematical abstraction we are interested in straight-line drawings of plane graphs realizing the prescribed faces areas. We say a plane graph is 'area-universal' if every area assignment to the inner faces has a realizing straight-line drawing. In the beginning of this thesis, not much was known. Specifically, there were three interesting facts: On the positive side, stacked triangulations and plane cubic graphs are area-universal. On the negative side, it is known that the octahedron is not area-universal. The aim of this thesis is to shed some more light into the world of area-universal graphs. The work is structured as follows: *Chapter 1: Introduction.* The concept of area-universality is introduced and the state of the art is presented. *Chapter 2: The Toolbox.* We introduce the basic notions and discuss properties of area-universal graphs. In particular, we introduce area-universality preserving operations and several characterizations of area-universality. These tools are used repeatedly throughout this thesis. *Chapter 3: Triangulations.* We study area-universality of maximal plane graphs, i.e., triangulations, and develop methods to prove and disprove area-universality. For the octahedron graph, we present a new proof technique to disprove its area-universality. Our proof relies on a simple counting argument that can also be used to show that no 'Eulerian triangulation' is area-universal. The result has several interesting consequences. Among them, there is no hope for constant factor approximations of realizing drawings even in the set of 4-connected triangulations. Adding some geometric arguments, a similar reasoning can be used for disproving the area-universality of other graphs. Moreover, we develop a sufficient criterion to guarantee the area-universality of triangulations with a special vertex order. The criterion relies on the investigation of area assignment. Combining these two techniques, we can characterize the area-universality of an interesting 4-connected family of triangulations. *Chapter 4: Quadrangulations.* We study the conjecture that all quadrangulations are area-universal. Even though we do not provide a full answer, we establish the area-universality of large classes of quadrangulations via reductions to related area-universal graphs. From our results it follows that a minimal counter example to the conjecture has at least 14 vertices. *Chapter 5: Drawings with Bends.* Given that not all plane graphs are area-universal, we investigate how much the straight-line property must be relaxed to realize each area assignment of every plane graph. We show that the 1-subdivision of every planar graph is area-universal, i.e., one bend per edge is sufficient. *Chapter 6: Related Concepts.* In this chapter, we study related concepts, in particular convex realizing drawings, equiareal drawings and realizing drawings for area assignments with negative values; in the latter case the drawings are not necessarily crossing-free. *Chapter 7: Computational Complexity.* We investigate the computational complexity of area-universality and present several interesting connections to the complexity class 'universal existential theory of the reals'. In particular, we show hardness of several variants of area-universality. *Chapter 8: Future Direction -- Air Pressure.* We transfer the idea of the air pressure method, which has previously been used in the context of area-universal rectangular layouts and seems promising to show area-universality of cubic graphs or other graph classes. *Chapter 9: Open Problems and Conjectures.* We conclude with our favorite set of open questions and ideas for further projects related to the study of plane graphs and faces areas., Die Arbeit beschäftigt sich mit planaren Graphen und vorgegebenen Flächeninhalten, die zum Beispiel im Bereich verzerrter Karten auftreten. Ein Kartogramm ist eine deformierte Karte, in der die Fläche jeder Region proportional zur Einwohnerzahl, der Geburtenrate oder eines anderen statistischen Parameters ist. Bisher wurden Kartogramme vor allem als proportionale Kontaktdarstellungen abstrahiert. Wir betrachten eine andere Abstraktion, bei der ein planar eingebetteter Graph mit Flächeninhalten für die inneren Flächen gegeben ist und suchen eine geradlinige Zeichnung, in der die gewünschten Flächeninhalte realisiert werden. Ein Graph heißt 'flächenuniversell', wenn für jede beliebige Flächeninhaltszuweisung eine realisierende geradlinige Zeichnung existiert. Dieses auch sehr natürliche Konzept ist bisher weit weniger untersucht. Die bekannten Fakten lassen sich leicht zusammen fassen: Es gibt einen Graphen, den Oktaedergraph, der nicht flächenuniversell ist und zwei Klassen flächenuniverseller Graphen, die planar eingebetten kubischen Graphen und die partiellen 3-Bäume. Als Ziel dieser Arbeit wollen wir einen tieferen Einblick in die Welt flächenuniverseller Graphen erhalten. Die Arbeit gliedert sich wie folgt: *Kapitel 1: Einleitung.* Das Konzept der Flächenuniversalität wird eingeführt und ein Überblick des aktuellen Forschungsstands präsentiert. *Kapitel 2: Der Werkzeugkasten.* Wir beschreiben die grundlegenden Konzepte und Eigenschaften von flächenuniversellen Graphen und Operationen, bei denen die Flächenuniversalität erhalten bleibt. Des Weiteren geben wir mehrere Charakterisierungen an, die wir im Laufe der Arbeit verwenden um Flächenuniversalität zu beweisen oder zu widerlegen. *Kapitel 3: Triangulierungen.* Wir entwickeln Techniken um die Flächenuniversalität von Triangulierungen zu beweisen und zu wiederlegen. Für den Oktaedergraph präsentieren wir ein einfaches Zählargument, dass die Flächenuniversalität widerlegt. Dieses lässt sich auf alle Eulerschen Triangulierungen anwenden. Kombiniert mit geometrischen Argumenten, lässt sich das Zählargument auch bei weiteren Graphen nutzen. Als Schlussfolgerung besitzen planare Graphen im Allgemeinen keine Zeichnungen, die die Flächeninhalte wenigstens mit einem konstanten Faktor approximieren. Des Weiteren entwickeln wir ein hinreichendes Kriterium, was auf der Analyse einer Flächenzuweisung beruht, um die Flächenuniversalität von Triangulierungen mit speziellen Kontenreihenfolgen zu garantieren. Vereint, erlauben uns diese Instrumente unter anderem die Flächenuniversalität einer interessanten Familie zu charakterisieren. *Kapitel 4: Quadrangulierungen.* In diesem Kapitel studieren wir die Vermutung, dass Quadrangulierungen flächenuniversell sind. Mit Hilfe von Reduktionen auf verwandte flächenuniverselle Graphen zeigen wir die Flächenuniversalität großer Familien von Quadrangulierungen und bestätigen die Vermutung für Quadrangulierungen mit bis zu 13 Knoten. *Kapitel 5: Zeichnungen mit Knicken.* Da nicht alle planaren Graphen flächenuniversell sind, untersuchen wir, wie stark die Geradlinigkeit relaxiert werden muss, um für jeden planar eingebetteten Graphen und jede Flächenzuweisung eine realisierende Zeichnung zu finden. Wir zeigen, dass jede 1-Subdivision flächenuniversell ist, daher benötigen realisierende Zeichnungen höchstens einen Knick pro Kante. *Kapitel 6: Verwandte Konzepte.* In diesem Kapitel untersuchen wir verwandte Konzepte, insbesondere konvexe realisierende und gleichflächige Zeichnungen, sowie realisierende Zeichnungen für Flächenzuweisungen, die negative Werte beinhalten. Im letzten Fall sind die Zeichnungen im Allgemeinen nicht kreuzungsfrei. *Kapitel 7: Komplexität.* Wir untersuchen die Komplexität des Entscheidungsproblem, ob ein gegebener Graph flächenuniversell ist, und zeigen interessante Zusammenhänge zu der Komplexitätsklasse 'universal existential theory of the reals'. Insbesondere zeigen wir, dass verschiedene Varianten dieses Problems vollständig für diese Komplexitätsklasse sind. *Kapitel 8: Die Luftdruck-Methode.* Wir übertragen die Idee der Luftdruck-Methode, die bereits im Kontext flächenuniverseller Rechteckszerlegungen betrachtet wurde, in unser Modell. *Kapitel 9: Offene Fragen und Vermutungen.* Abschließend präsentieren wir eine Auswahl interessanter offener Fragen für zukünftige Projekte im Bereich von planaren Graphen und Flächeninhalten.

This thesis focuses on the solution of high dimensional Hermitian eigenproblems in situations where vector operations cannot be carried out exactly. To this end an inexact Arnoldi method with the aim to approximate extreme eigenvalues and eigenvectors is developed. This method is particularly wellsuited for large scale problems as it efficiently reduces the storage and computational requirements by constructing an orthonormal basis of the associated Krylov subspace. To consider the effect of the inexactness of the operations, a variant of Gram Schmidt orthogonalization is introduced in this thesis. The so called compensated Gram Schmidt orthogonalization (ComGS), if necessary enhanced by reorthogonalization, is used in the inexact Arnoldi method to compute a nearly orthogonal basis of the associated Krylov subspace. The effects of small perturbations on the distance to orthogonality of the resulting basis are studied and the ComGS method is compared to classical methods such as the modified and classical Gram Schmidt method. To investigate the influence of the inexactness of the vector operations not only on the orthogonality of the Krylov subspace basis but also on the quality of the spectral approximations, the convergence behavior of the inexact Arnoldi method and more general of inexact Krylov subspace methods is analyzed. By using the concept of the angle of inclusion, bounds for the distance of the exact invariant subspace to (i) an inexact Krylov subspace and (ii) a Ritz space therein are found. While based on the first bound an a priori statement about how many more iteration steps of the inexact Krylov method are necessary to ensure convergence to a given tolerance can be derived, the second bound allows for an a posteriori statement regarding the quality of the computed Ritz space. To avoid the sensitivity of both bounds to the gap between the desired and the remaining eigenvalues the concept of nested subspaces is used in the a priori setting whereas in the a posteriori setting the Ritz space is allowed to be of larger dimension than the invariant subspace. Consequently, the bounds can be valid and meaningful even in the presence of perturbations and a small gap between the desired and remaining eigenvalues. Lastly, the inexact Arnoldi method is generalized to the tensor setting to make storage and computations feasible. Numerical experiments with the YZ-model show that in the operator-tensor setting the inexact Arnoldi method allows for the solution of quantum systems of much larger dimension than it would be possible in the matrix-vector setting., In dieser Arbeit werden Lösungsverfahren für hochdimensionale Hermitesche Eigenwertprobleme unter Berücksichtigung von inexakten Vektoroperationen untersucht. Zu diesem Zweck wird eine inexakte Arnoldi Methode zur approximativen Berechnung extremer Eigenwerte und Eigenvektoren entwickelt. Diese Methode ist besonders für hochdimensionale Probleme geeignet, da sie den Speicher- und Rechenaufwand durch den Aufbau einer orthonormalen Basis des zugehörigen Krylovraumes reduziert. Um die Auswirkungen inexakter Operationen zu berücksichtigen, wird in dieser Dissertation eine Variante der Gram Schmidt Orthogonalisierung, die so genannte compensated Gram-Schmidt Orthogonalisierung (ComGS), vorgestellt. Diese Methode (ggf. ergänzt durch Reorthogonalisierung) wird in der inexakten Arnoldi Methode verwendet, um eine nahezu orthogonale Basis des zugehörigen Krylovraumes zu berechnen. Es werden die Auswirkungen der Störungen auf den Orthogonalitätsabstand der resultierenden Basis untersucht und die ComGS Methode mit klassischen Orthogonalisierungsverfahren verglichen. Um nicht nur die Auswirkungen der inexakten Vektoroperationen auf die Orthogonalität der Krylov-Unterraumbasis, sondern auch auf die Qualität der spektralen Approximationen zu untersuchen, wird das Konvergenzverhalten der inexakten Arnoldi Methode und allgemein der inexakten Krylov-Unterraumraum-Verfahren analysiert. Unter Verwendung des Konzepts Angle of inclusion werden Schranken für den Abstand des invarianten Teilraums zu (i) einem inexakten Krylov-Unterraum und (ii) zu einem Ritz-Raum, welcher im inexakten Krylov-Unterraum enthalten ist, gefunden. Basierend auf der ersten Schranke kann eine a priori Aussage gemacht werden, wie viele zusätzliche Iterationsschritte der inexakten Krylov Methode notwendig sind, um die Konvergenz zu einer gegebenen Toleranz zu gewährleisten. Die zweite Schranke ermöglicht eine a posteriori Aussage über die Qualität des berechneten Ritz-Raums. Um die Sensitivität beider Schranken hinsichtlich des Abstandes zwischen den gesuchten Eigenwerten und dem restlichen Spektrum zu vermeiden, wird in der Herleitung der a priori Schranke das Prinzip verschachtelter Unterräume verwendet, während in der Herleitung der a posteriori Schranke der betrachtete Ritz-Raum eine größere Dimension als der gesuchte invariante Teilraum haben darf. Die hergeleiteten Schranken sind somit auch gültig und aussagekräftig, falls die Matrix einer Störung unterliegt oder ihr Spektrum einen kleinen Abstand zwischen den gesuchten und restlichen Eigenwerten aufweist. Schließlich wird die inexakte Arnoldi Methode auf Tensoren übertragen. Numerische Experimente mit dem YZ-Modell zeigen, dass im Operator-Tensor-Setting die inexakte Arnoldi Methode die Lösung des Eigenwertproblems von Quantensystemen deutlich höherer Dimensionen ermöglicht, als es im Matrix-Vektor-Setting möglich wäre.

Harmonic Balance is a very popular semi-analytic method in nonlinear dynamics. It is easy to apply and is known to produce good results for numerous examples. Adding an error criterion taking into account the neglected terms allows an evaluation of the results. Looking on the therefore determined error for increasing ansatz orders, it can be evaluated whether a solution really exists or is an artifact. For the low-error solutions additionally a stability analysis is performed which allows the classification of the solutions in three types, namely in large error solutions, low error stable solutions and low error unstable solution. Examples considered in this paper are the classical Duffing oscillator and an extended Duffing oscillator with nonlinear damping and excitation. Compared to numerical integration, the proposed procedure offers a faster calculation of existing multiple solutions and their character.

Free-variables categorical cartesian theories: Interpretation of free variables as identitic maps or projections. Iteration, full schema of primitive recursion, Hilbert's infnite hotel, Algebra and order on the Natural Numbers Object N.

We are tackling the problem of reducing high congestion in networks from a mathematical point of view. First, we consider resource allocation problems where a set of commodities jointly uses a set of resources. The feasible allocations for each commodity are a commodity specific set of subsets of resources. The cost of each resource is determined by a polynomial function with maximum degree d that depends on the number of comodities using it. We propose a local search algorithm to reduce the overall cost for which we provide an upper and corresponding lower bound on the locality gap. In addition, we give concrete values for the locality gap for small d. We also evaluate the general approximation guarantee for the linear case and show APX-hardness with a lower bound that rises if the Unique Games Conjecture holds true. Further, we consider impartial selection, where a set of agents cast nominations amongst themselves and we seek to select an agent with a high number of nominations. Each selection mechanism shall maintain impartiality, meaning that a user’s nominations have no influence on her probability of being selected. While it has been shown that no deterministic exact mechanism can guarantee any positive approximation factor, we relax the exactness requirement and allow to sometimes, but not always select less than the desired number of agents. We introduce a mechanism which achieves a best possible result for deterministically selecting up to two agents. In the randomized variant, a performance guarantee for the expected number of nominations is given. We give a best possible mechanism for the case of selecting up to two out of three agents. We also introduce upper and lower bounds for exactly selecting two agents. Further, we generalize and subsequently analyze our algorithms to select a larger number of k agents. In addition, our work provides a general allocation subroutine, which gives a quick, simple solution to the problem of fairly allocating representatives in proportion to group sizes. Finally, we consider the online dial-a-ride problem on the line. Users arrive in an online manner in some place on the real line and request to be transported to another place on the line. A server of given capacity which starts at the origin picks users up and delivers them, with or without temporary interruption, to their destination. Our goal is to minimize the makespan, i.e. the time which the server needs until the last request is fulfilled. We provide a competitive algorithm for preemptive online dial-a-ride on the line and we prove an improved lower bound for the non-preemptive setting. In addition, we show that a slightly modified version of the algorithm holds the competitive ratio in metric space. We also consider the offline problem and prove that we can construct instances such that the server has to make direction changes on the line arbitrarily often and give a dynamic program which computes the minimum completion time in quadratic time. Further, we show that in contrast to that, the non-preemptive offline dial-a-ride on the line with capacity one is NP-complete., In dieser Arbeit betrachten beschäftigen wir uns mit dem Problem der Reduzierung von starker Auslastung in Netzwerken. Zuerst betrachten wir allgemeine Ressourcenverteilungsprobleme, in welchen Nutzer gemeinsam eine Menge von Ressourcen mit negativen Skaleneffekten benutzt. Die zulässigen Verteilungen für jeden Nutzer bestehen aus einer nutzerspezifische Menge von Teilmengen der Ressourcen. Die Kosten für jede Ressource sind durch ein Polynom der Ordnung d bestimmt, welches die Gesamtnutzung einer Ressource auf ihre Kosten abbildet. Wir präsentieren einen lokalen Suchalgorithmus zur Reduzierung der Gesamtkosten für welchen wir eine obere und untere Schranke an die Lokalisierungslücke angeben. Zusätzlich geben wir konkrete Werte der Lokalisierungslücke für kleine d. Wir berechnen außerdem die allgemeine Approximationsgarantie für den linearen Fall und zeigen APX-Schwere mit einer unteren Schranke welche sich erhöht falls die Unique Games Vermutung wahr ist. Weiterhin betrachten wir das Problem der unabhängigen Auswahl, bei dem sich eine Menge von Spielern untereinander nominiert und wir eine Spielerin mit einer großen Anzahl von Nominierungen auswählen wollen. Jeder Auswahlmechanismus soll Unabhängigkeit sichern, das heißt, dass die Nominierungen einer Spielerin keinen Einfluss auf ihre Wahrscheinlichkeit ausgewählt zu werden haben. Es ist bekannt, dass kein deterministischer Mechanismus eine positive Approximationsgüte garantieren kann, weswegen wir die Exaktheitsbedingung lockern und erlauben, dass manchmal, aber nicht immer, auch weniger als die vorgegebene Menge an Spielern ausgewählt werden kann. Wir führen einen Mechanismus ein, welcher ein bewiesen bestmögliches Ergebnis für die deterministische Auswahl von bis zu zwei Spielern gibt. Für die randomisierte Variante geben wir eine Garantie für die Anzahl von Nominierungen in Erwartung. Weiterhin zeigen wir einen bestmöglichen Mechanismus für die Auswahl von bis zu zwei aus drei Spielern. Wir geben zudem untere und obere Schranken um genau zwei Spieler auszuwählen und verallgemeinern und analysieren unsere Mechanismen für die Auswahl einer größeren Anzahl von k Spielern. Zusätzlich gibt unsere Arbeit eine Zuteilungsunterroutine, welche eine schnelle und einfache Lösung für das Problem auf faire Art und Weise Repräsentanten proportional zu Gruppengrößen auszuwählen bietet. Schließlich betrachten wir das online Fahrdienstproblem auf der Linie. Nutzer erscheinen in einer fortlaufenden Art und Weise an einer beliebigen Stelle auf dem reellen Zahlenstrahl und fragen an, zu einem anderen Ort auf dem Zahlenstrahl transportiert zu werden. Ein Zusteller mit vorgegebener Kapazität, welcher im Nullpunkt startet, nimmt die Nutzer auf und bringt sie, mit oder ohne temporäre Unterbrechung, zu ihrem Ziel. Unser Ziel ist es, die Gesamtdauer, d.h. die Gesamtzeit, welche der Server braucht bis der letzte Auftrag ausgeführt wurde, zu minimieren. Wir präsentieren einen kompetitiven Algorithmus für das online Fahrdienstproblem mit Unterbrechungen auf der Linie und beweisen eine verbesserte untere Schranke für den Fall ohne Unterbrechungen. Weiterhin zeigen wir, dass eine leicht modifizierte Variante des Algorithmus die Kompetitivitätsgüte beibehält. Wir betrachten zudem das offline Problem und zeigen, dass wir Instanzen konstruieren können, so dass der Server beliebig viele Richtungswechsel auf der Linie machen muss und geben ein dynamisches Programm an, welches die minimale Vollendungszeit für dieses Problem in quadratischer Zeit berechnet. Im Gegensatz hierzu zeigen wir, dass das offline Fahrdienstproblem ohne Unterbrechungen mit Kapazität eins NP-vollständig ist.

Many parts of our daily routine that we expect to "just work" rely on certain optimization processes that most of the time take place in a network. Ranging from streets, railroads or power networks to the telecommunications network used by the Internet and the networks induced by social networks: the list of structures that can be modeled as a network goes on and on and optimization processes on these networks are vital throughout our daily life. In many network optimization problems the goal is to transport a commodity through the network in an efficient manner, e.g., people, objects, or more abstract commodities like the information you receive over a social network, or the movie you want to stream. Often a huge amount of the same commodity needs to be transported at once, like the large number of newspapers that are delivered each morning, the amount of data that travels through the communications network when you stream the latest episode of your favorite TV show, or the electricity that is needed to power the local hospital. Such transportation problems gave rise to the development of static network flows more than 90 years ago. For many optimization problems on networks it is essential that a certain deadline is met and also that it takes time for a commodity to travel along an arc of the network, e.g. a street or a power cable. Such properties are not incorporated in the classical static network model. Here dynamic networks and flows over time come into play which are capable of modeling temporal aspects of transportation problems. In this thesis we study such network flows over time. In particular we concentrate on two classical flow over time problems that are especially useful in the context of evacuation planning. For both problems we give new and more efficient algorithms for solving them that exploit connections between the specific flow over time problem and suitably chosen submodular functions. When evacuating people from a dangerous situation the main objective that comes to mind immediately is to save all people as quickly as possible. This property is incorporated by quickest transshipments, which are the first class of flows over time that we concentrate on throughout this thesis. In the quickest transshipment problem we are given a dynamic network with sources and sinks, and supplies and demands, respectively, and the goal is to find a flow over time that fulfills these supplies and demands as quickly as possible. The first main result in this thesis is a new strongly polynomial time algorithm for the quickest transshipment problem that significantly improves upon the so far best known algorithm for this problem, the algorithm by Hoppe and Tardos. Our algorithm exploits a connection between quickest transshipments and certain submodular functions and we use this connection to show that a solution to the quickest transshipment problem can essentially be found by only one parametric submodular function minimization. With our algorithm we achieve the first improvement for solving the quickest transshipment problem in more than 20 years. When evacuating people using quickest transshipments, all people are rescued as quickly as possible. However, in many dangerous situation it is not clear, when the actual disaster will occur, e.g. after a bomb threatening it is usually not known if or when the bomb will detonate. In such a situation evacuating people using quickest transshipments is not a good idea as it is not clear whether it is even possible to evacuate all people. Better suited for such situations are earliest arrival transshipments, which additionally have the property that as much flow as possible has arrived at the sinks at every point in time simultaneously. Thus, even if it is not possible to save all endangered people, when using earliest arrival transshipments, it is at least ensured that as many people as possible are rescued. However, the problem with earliest arrival transshipments is that they do not always exist. Furthermore, it is unlikely that polynomial time algorithms for earliest arrival transshipment problems do exist as it was recently shown that computing them is NP-hard. One special case of dynamic networks in which earliest arrival transshipments do exist in general, are dynamic networks with only a single sink. For this special class of networks we present the first polynomial space algorithm for solving earliest arrival transshipment problems. In particular our algorithm does not require any form of expansion of the original dynamic network. This solves a problem which has been open for more than ten years. In dynamic networks with multiple sinks, earliest arrival transshipments do not exist in general and so far not much research has been put into developing efficient algorithms for computing earliest arrival transshipments in multiple sink networks (in case of existence). We present the first polynomial space algorithm that checks whether an earliest arrival transshipment does exist and computes it in case of existence for the special case of earliest arrival transshipment problems in dynamic networks with multiple sinks and a single source, and tight problems in general networks., Viele Aspekte unseres Alltags, von denen wir erwarten, dass sie "einfach funktionieren", sind auf bestimmte Optimierungsprozesse angewiesen, die oft in einem Netzwerk stattfinden. Von Straßennetzen, Eisenbahnnetzen oder Stromnetzen bis hin zum Telekommunikationsnetz des Internets und den von sozialen Netzwerken induzierten Netzwerken: Die Liste der Strukturen, die als Netzwerke modelliert werden können, ist lang und Optimierungsprozesse in diesen Netzwerken sind essenziell in unserem täglichen Leben. In vielen Netzwerkoptimierungsproblemen besteht das Ziel darin, Dinge effizient durch das Netzwerk zu transportieren, z. B. Menschen, Objekte oder abstraktere Dinge wie die Informationen, die Sie über ein soziales Netzwerk erhalten oder den Film, den man streamen möchte. Oft muss eine große Menge des gleichen Gutes auf einmal transportiert werden, wie die große Anzahl von Zeitungen, die jeden Morgen geliefert werden, die Menge an Daten, die durch das Kommunikationsnetz fließen, wenn man die letzte Folge der Lieblingsfernsehsendung streamt, oder die Elektrizität, die benötigt wird, um das örtliche Krankenhaus zu versorgen. Solche Transportprobleme führten vor mehr als 90 Jahren zur Entwicklung von statischen Netzwerkflüssen. Im Kontext vieler Optimierungsprobleme in Netzwerken ist es wesentlich, dass eine bestimmte Frist eingehalten wird und dass es Zeit braucht, eine Ware entlang einer Kante des Netzes, z.B. entlang einer Straße oder eines Stromkabels, zu transportieren. Solche Eigenschaften sind im klassischen statischen Netzwerkmodell nicht enthalten. Hier kommen dynamische Netzwerke und zeitabhängige Flüsse zum Tragen, die in der Lage sind, zeitliche Aspekte von Transportproblemen zu modellieren. In dieser Arbeit untersuchen wir solche zeitabhängigen Flüsse. Insbesondere konzentrieren wir uns auf zwei klassische zeitabhängige Flussprobleme, die besonders im Kontext der Evakuierungsplanung nützlich sind. Für beide Probleme präsentieren wir neue und effizientere Algorithmen für deren Lösung, welche Verbindungen zwischen dem spezifischen Flussproblem und geeignet ausgewählten submodularen Funktionen ausnutzen. Wenn man Menschen aus einer gefährlichen Situation evakuiert, ist es das wichtigste Ziel, alle Menschen so schnell wie möglich zu retten. Diese Eigenschaft wird von Quickest-Transshipments modelliert, der ersten Klasse von zeitabhängigen Flüssen, auf die wir uns in dieser Arbeit konzentrieren. Der Input eines Quickest-Transshipment-Problems ist ein dynamisches Netzwerk mit Quellen und Senken mit Angebot und Nachfrage und das Ziel ist es, einen zeitabhängigen Fluss zu finden, der Angebot und Nachfrage so schnell wie möglich erfüllt. Das erste Hauptresultat in dieser Arbeit ist ein neuer stark polynomieller Algorithmus für das Quickest-Transshipment-Problem, der den bisher besten Algorithmus für dieses Problem, den Algorithmus von Hoppe und Tardos, wesentlich verbessert. Unser Algorithmus nutzt eine Verbindung zwischen Quickest-Transshipments und bestimmten submodularen Funktionen aus und wir beweisen, dass eine Lösung für das Quickest-Transshipment-Problem im Wesentlichen nur durch eine parametrische Minimierung einer parametrisierten submodularen Funktion gefunden werden kann. Mit unserem Algorithmus erreichen wir die erste Verbesserung für das Lösen des Quickest-Transshipment-Problems in mehr als 20 Jahren. Bei der Evakuierung von Personen mit Quickest-Transshipments werden alle Menschen so schnell wie möglich gerettet. In vielen gefährlichen Situationen ist jedoch nicht klar, wann die tatsächliche Katastrophe eintreten wird, z.B. ist nach einer Bombendrohung nicht bekannt, ob und wann genau die Bombe explodieren wird. In einer solchen Situation ist die Evakuierung von Menschen mit Quickest-Transshipments eine schlechte Strategie, da man nicht weiß, ob es überhaupt möglich ist, alle Menschen zu evakuieren. Besser geeignet für solche Situationen sind Earliest-Arrival-Transshipments, die zusätzlich die Eigenschaft haben, dass sie an jedem Zeitpunkt maximal sind, also, dass zu jedem Zeitpunkt so viel Fluss wie möglich an den Senken angekommen ist. Selbst wenn es nicht möglich ist, alle gefährdeten Personen zu retten, ist bei der Verwendung von Earliest-Arrival-Transshipments zumindest sichergestellt, dass so viele Menschen wie möglich gerettet werden. Ein Problem im Kontext von Earliest-Arrival-Transshipments ist allerdings, dass sie nicht immer existieren. Darüber hinaus ist es unwahrscheinlich, dass polynomielle Algorithmen für Earliest-Arrival-Transshipment-Probleme existieren, denn es wurde kürzlich gezeigt, dass ihre Berechnung NP-schwer ist. Ein spezieller Fall von dynamischen Netzwerken, in denen Earliest-Arrival-Transshipments immer existieren, sind dynamische Netzwerke mit nur einer einzigen Senke. Für diese spezielle Klasse von Netzwerken präsentieren wir den ersten PSPACE Algorithmus für die Lösung von Earliest-Arrival-Transshipment-Problemen. Insbesondere benötigt unser Algorithmus keine Form der Expandierung des ursprünglichen dynamischen Netzwerks. Dies löst ein Problem, das seit mehr als zehn Jahren offen ist. In dynamischen Netzwerken mit mehreren Senken gibt es im Allgemeinen keine Earliest-Arrival-Transshipments. Deshalb wurde bisher nicht viel Forschung in die Entwicklung effizienter Algorithmen zur Berechnung von Earliest-Arrival-Transshipments in Netzwerken mit mehreren Senken investiert (für den Fall, dass diese existieren). In dieser Arbeit präsentieren wir den ersten PSPACE Algorithmus, der prüft, ob ein Earliest-Arrival-Transshipment existiert und ein solches Transshipment im Falle der Existenz berechnet für den Spezialfall von dynamischen Netzwerken mit nur einer Quelle und mehreren Senken und für spezielle Earliest-Arrival-Transshipment-Probleme in allgemeinen Netzwerken.

This thesis addresses classical lattice point problems in discrete and convex geometry. Integer points in convex bodies are the central objects of our studies. In the second chapter, we will prove bounds on the number of lattice points in centered convex bodies. The underlying problems are motivated by classical results in geometry of numbers. We will show that the assumption of centricity yields asymptotically comparable bounds to those which are known and well-studied for symmetric convex bodies. Moreover, by developing an approach which links lattice points in a simplex to its barycentric coordinates, the best possible upper bound for the number of lattice points in centered simplices is deduced. The third chapter is devoted to expanding Ehrhart theory to tensor-valued Ehrhart theory. This will become apparent to be a natural generalization of the classical theory. We will examine the coefficients of the Ehrhart tensor and hr -tensor polynomials and deduce Pick-type formulas in the plane, which depend on the edge graph of the given polygon. It is an intriguing problem to extend the notion of nonnegativity to tensor-valued coefficients with regard to Stanley’s nonnegativity theorem. Therefore, a variant of Stanley’s result for rank 2 tensors in the plane will be shown; here, the notion of nonnegativity is aligned with positive semidefiniteness of matrices. It is conjectured that this also holds in higher dimensions as well. Finally, a new characterization of reflexive polytopes depending on the palindromicity of hr -tensors is given, extending a result due to Hibi. Chapter 4 deals with discrete John-type theorems, which say that the integer points in a symmetric convex body can be approximated by a symmetric generalized arithmetic progression, or symmetric GAP for short. This represents an intuitive discretization of the famous result due to John that a symmetric convex body in d dimensions can be enclosed between an ellipsoid and its multiple by a factor of the square root of d. Tao and Vu showed that the same can indeed be done in the discrete case with a factor depending only on d. Moreover, Tao and Vu provided upper bounds for the number of lattice points in a given symmetric convex body in terms of the contained symmetric GAP. In this chapter, we will improve both results significantly. To this end, we study symmetric GAPs and their properties elaborately. Furthermore, we will discuss possible extreme cases leading to lower bounds. Chapter 5 focuses on discrete slicing inequalities. In general, these involve bounding the discrete volume of a convex body K concerning the maximal number of lattice points in the intersection of K with linear or affine subspaces. It is discussed how the well-known Brunn’s inequality can be discretized. We also prove a fully-discretized slicing inequality exclusively involving the discrete volume. In particular, we will establish lattice point bounds for sym- metric convex bodies regarding their maximal one-dimensional slices. This yields a discrete, one-dimensional Furstenberg-Tzkoni inequality., Diese Dissertation befasst sich mit klassischen Gitterpunktproblemen aus der diskreten und konvexen Geometrie. Ganzzahlige Punkte in konvexen Körpern sind die zentralen Objekte unserer Untersuchungen. Im zweiten Kapitel werden wir Abschätzungen für die Anzahl der Gitterpunkten in zentrierten konvexen Körpern herleiten. Das zugrunde liegende Problem ist dabei motiviert von klassischen Resultaten aus der Geometrie der Zahlen. Wir werden zeigen, dass die Annahme der zentralen Lage eines konvexen Körpers Abschätzungen liefert, welche asymptotisch vergleichbar sind zu denen, die für symmetrische konvexe Körper bekannt sind. Indem ein Ansatz entwickelt wird, der ganzzahlige Punkte zu deren baryzentrischen Koordinaten in Verbindung setzt, werden best- mögliche Schranken für zentrierte Simplizes bewiesen. Das dritte Kapitel ist der Erweiterung der Ehrhart Theorie zu tensorwertiger Ehrhart Theorie gewidmet. Dies wird sich als natürliche Verallgemeinerung der klassischen Theorie herausstellen. Wir werden die Koeffizienten der Ehrhart Tensoren und der hr -Tensor Polynome untersuchen und, ausgehend vom Kantengraphen eines Polygons, tensorwertige Varianten von Picks Theorem vorstellen. Ein bemerkenswertes Problem ist die Verallgemeinerung des Begriffes der Nichtneg- ativität für tensorwertige Koeffizienten in Hinblick auf Stanleys Nichtnegativitätstheorem. Eine entsprechende Variante von Stanleys Theorem für Tensoren von Rang 2 in der Ebene wird er- arbeitet, für welche der Begriff der Nichtnegativität mit dem der positiven Semidefinitheit für Matrizen zusammenfällt. Es wird zudem vermutet, dass dieses Resultat auch in höheren Di- mensionen gültig ist. Schließlich wird eine neue Charakterisierung reflexiver Polytope bezüglich der palindromischen Eigenschaft von hr -Tensoren vorgestellt, wodurch ein Resultat von Hibi verallgemeinert wird. Kapitel 4 behandelt diskrete John Theoreme, welche aussagen, dass die ganzzahligen Punkte in einem symmetrischen konvexen Körper durch symmetrische verallgemeinerte arithmetische Progressionen (im Folgenden kurz: arithmetische Progression) approximiert werden können. Dies bildet eine intuitive Diskretisierung des bekannten Satzes von John, welcher aussagt dass ein symmetrischer konvexer Körper in d Dimensionen zwischen einem Ellipsoid und dessen Vielfachen zum Faktor der Quadratwurzel aus d eingeschlossen werden kann. Tao und Vu haben gezeigt, dass dies ebenso mittels einer arithmetischen Progression, und einem Faktor abhängig von d, möglich ist. Zudem präsen- tierten Tao und Vu obere Schranken für die Anzahl ganzzahliger Punkte in einem symmetrischen konvexen Körper bezüglich einer in diesem enthaltenen arithmetischen Progression. In diesem Kapitel werden wir beide Resultate wesentlich verbessern. Dazu werden wir arithmetische Pro- gression und deren Eigenschaften ausführlich untersuchen. Desweiteren werden mögliche Ex- tremfälle diskutiert, welche ebenfalls untere Schranken liefern. Kapitel 5 konzentriert sich auf discrete slicing Ungleichungen. Allgemein beinhalten diese das Abschätzen ganzzahliger Punkte in einem konvexen Körper K in Abhängigkeit zu der maximalen Gitterpunktanzahl in dem Schnitt von K mit einem linearen oder affinen Unterraum. Es wird erörtert, wie die bekannte Brunns Ungleichung diskretisiert werden kann. Wir werden ebenso eine vollständig diskretisierte slicing Ungleichung beweisen, in der lediglich das diskrete Volumen vorkommt. Desweiteren wird insbesondere die Frage nach Gitterpunktabschätzungen bezüglich eindimensionaler Unterräume vollständig beantwortet werden können. Daraus ergibt sich zudem eine diskrete Furstenberg-Tzkoni Ungleichung.

Dieser Beitrag ist mit Zustimmung des Rechteinhabers aufgrund einer (DFG geförderten) Allianz- bzw. Nationallizenz frei zugänglich., This publication is with permission of the rights owner freely accessible due to an Alliance licence and a national licence (funded by the DFG, German Research Foundation) respectively., We describe algorithms for computing eigenpairs (eigenvalue-eigenvector pairs) of a complex n×n matrix A. These algorithms are numerically stable, strongly accurate, and theoretically efficient (i.e., polynomial-time). We do not believe they outperform in practice the algorithms currently used for this computational problem. The merit of our paper is to give a positive answer to a long-standing open problem in numerical linear algebra.

M focus inferior von E. focinf M. efocinf M. M focus superior von E. focsup M. efocsup M. M focus von E. foc M. efoc M. Filter-Basis. (M,E) gw inferior von x. gwinf(M,E). egwinf(M,E). (M,E) gw superior von x. gwsup(M,E). egwsup(M,E). (M,E) gw von x. gw(M,E). egw(M,E). E upkt p. (M,E) limes inferior von x in p. liminf (M,E)(x,p). eliminf (M,E)(x,p). (M,E) limes superior von x in p. limsup (M,E)(x,p). elimsup (M,E)(x,p). (M,E) limes ordinatus von x in p. limord (M,E)(x,p). elimord (M,E)(x,p). Modellierung: Generation und Abbau II. Zeitdiskretes Modell. R ist ana1 von q,x. rf1qx.

In this paper, we consider the conductivity problem with piecewise‐constant conductivity and Robin‐type boundary condition on the interface of discontinuity. When the quantity of interest is the jump of the conductivity, we perform a local stability estimate for a parameterized non‐monotone family of domains. We give also a quantitative stability result of local optimal solution with respect to a perturbation of the Robin parameter. In order to find an optimal solution, we propose a Kohn–Vogelius‐type cost functional over a class of admissible domains subject to two boundary values problems. The analysis of the stability involves the computation of first‐order and second‐order shape derivative of the proposed cost functional, which is performed rigorously by means of shape‐Lagrangian formulation without using the shape sensitivity of the states variables.

We study the variational structure of the discrete Kadomtsev-Petviashvili (dKP) equation by means of its pluri-Lagrangian formulation. We consider the dKP equation and its variational formulation on the cubic lattice \(\mathbb Z^{N}\) as well as on the root lattice \(Q(A_{N})\). We prove that, on a lattice of dimension at least four, the corresponding Euler-Lagrange equations are equivalent to the dKP equation.

We discuss several extensions and applications of the theory of discretely conformally equivalent triangle meshes (two meshes are considered conformally equivalent if corresponding edge lengths are related by scale factors attached to the vertices). We extend the fundamental definitions and variational principles from triangulations to polyhedral surfaces with cyclic faces. The case of quadrilateral meshes is equivalent to the cross ratio system, which provides a link to the theory of integrable systems. The extension to cyclic polygons also brings discrete conformal maps to circle domains within the scope of the theory. We provide results of numerical experiments suggesting that discrete conformal maps converge to smooth conformal maps, with convergence rates depending on the mesh quality. We consider the Fuchsian uniformization of Riemann surfaces represented in different forms: as immersed surfaces in \(\mathbb {R}^{3}\), as hyperelliptic curves, and as \(\mathbb {CP}^{1}\) modulo a classical Schottky group, i.e., we convert Schottky to Fuchsian uniformization. Extended examples also demonstrate a geometric characterization of hyperelliptic surfaces due to Schmutz Schaller.

In this paper we discuss some partial solutions of the length conjecture which describes the length of a generating system for matrix algebras. We consider mainly the algebras generated by two matrices which are quasi-commuting. It is shown that in this case the length function is linearly bounded. We also analyze which particular natural numbers can be realized as the lengths of certain special generating sets and prove that for commuting or product-nilpotent pairs all possible numbers are realizable, however there are non-realizable values between lower and upper bounds for the other quasi-commuting pairs. In conclusion we also present several related open problems.

This paper considers the problem of computing the state reachable points, from the origin, of a linear constant coefficient descriptor system. A numerical algorithm is proposed that can be implemented to characterize the reachable set in a numerically stable way. The original descriptor system is transformed into a strangeness-free system within the behavioral framework followed by a projection that separates the system into its differential and algebraic parts. It is shown that the computation of the image space of two matrices, associated with the projected system, is enough to compute the reachable set (from the origin). Moreover, a characterization is presented of all the inputs by which one can reach to any arbitrary points in the reachable set. The effectiveness of the proposed approach is demonstrated through numerical examples.

Dieser Beitrag ist mit Zustimmung des Rechteinhabers aufgrund einer (DFG geförderten) Allianz- bzw. Nationallizenz frei zugänglich., This publication is with permission of the rights owner freely accessible due to an Alliance licence and a national licence (funded by the DFG, German Research Foundation) respectively., A bilevel shape optimization problem with the exterior Bernoulli free boundary problem as lowerlevel problem and the control of the free boundary as the upper-level problem is considered. Using the shape of the inner boundary as the control, we aim at reaching a specific shape for the free boundary. A rigorous sensitivity analysis of the bilevel shape optimization in the infinite-dimensional setting is performed. The numerical realization using two different cost functionals presented in this paper demonstrate the efficiency of the approach.

Book of Abstracts of the Workshop "Recent Trends in Differential Equations: Analysis and Discretisation Methods" 2013

Various asymptotic models for thin conducting sheets in computational electromagnetics describe them as closed hyper-surfaces equipped with linear local transmission conditions for the traces of electric and magnetic fields. The transmission conditions turn out to be singularly perturbed with respect to limit values of parameters depending on sheet thickness and conductivity. We consider the reformulation of the resulting transmission problems into boundary integral equations (BIE) and their Galerkin discretization by means of low-order boundary elements. We establish stability of the BIE and provide a priori $h$-convergence estimates, with the dependence on model parameters made explicit throughout. This is achieved by a novel technique harnessing truncated asymptotic expansions of Galerkin discretization errors.

Reversible Irrfahrten in zufälliger Umgebung (random walks in random environment, RWRE) werden Irrfahrten unter zufälligen Leitfähigkeiten (random walks among random conductances, RWRC) genannt und treten in vielen Teilbereichen der Wissenschaft als natürliche Modelle fuer physikalische Phänomene auf. In dieser Arbeit fuehren wir zuerst RWRC ein und heben dabei die Verbindungen zu elektronischen Netzwerken hervor. Gleichzeitig geben wir eine Übersicht über die existierende Literatur. Danach stellen wir unsere Ergebnisse vor. Zuerst geben wir einen Beweis fuer ein annealed Prinzip der großen Abweichungen (Large Deviation Principle, LDP) fuer die Lokalzeiten einer RWRC, die sich innerhalb einer Region mit festem Durchmesser befindet. Wir geben eine explizite Darstellung der Ratenfunktion an und erhalten durch das LDP asymptotische Formeln fuer die Wahrscheinlichkeiten der RWRC in der gegebenen Region zu bleiben. Dieses Ergebnis findet wichtige Anwendungen bei der Betrachtung von zufälligen Schrödinger-Operatoren und des parabolischen Anderson-Modells (Parabolic Anderson Model, PAM). Das zweite Resultat behandelt das Gesetz der grossen Zahlen fuer den Endpunkt eines RWRC. Wir zeigen, dass die asymptotische Geschwindigkeit fast sicher gleich Null ist, sobald die α-log Momente der Leitfähigkeiten fuer ein α > 1 endlich sind. Auf der anderen Seite implizieren endliche log Momente nicht Null-Geschwindigkeit: Wir geben ad hoc Gegenbeispiele mit Hilfe von geometrischen Konstruktionen zufälliger Bäume. Schließlich analysieren wir die Fluktuationen vom Minimum der Dirichlet Energie im zufaelligen Leitfähigkeits Modell. Diese Quantität, bekannt als effektive Leitfähigkeit (effective conductance), repräsentiert den totalen elektrischen Strom, der in einem elektrischen Netzwerk fließt, und spielt eine zentrale Rolle in der Homogenisierungstheorie. Wir beweisen einen zentralen Grenzwertsatz unter den Annahmen von Dirichlet-Randbedingungen und zufällige Leitfähigkeiten mit kleinem elliptischen Kontrast., Reversible random walks in random environment are called random walks among random conductances (RWRC) and they naturally arise in many branches of science as models for physical phenomena. In this thesis we first introduce RWRC, highlighting the connections with electrical networks, and give a substantial background on previous literature. Then, we present a series of original results. The first one is the proof of an annealed large deviation principle (LDP) for the local times of a RWRC forced to stay in a finite domain. We give an explicit expression for the rate function and obtain as a byproduct of the LDP asymptotic formulas for the non-exit probabilities from the given domain. This result has relevant applications in the parabolic Anderson model and in the study of random Schroedinger operators. The second result deals with the law of large numbers for the endpoint of a RWRC. We show that whenever the α-log moments of the conductances are finite for some α > 1, the limiting speed is zero almost surely. On the other hand, finite log moments for α < 1 do not imply zero speed: we construct ad hoc counterexamples based on geometrical constructions of random trees. Finally we analyze the fluctuations of the minimum of the Dirichlet energy in the random conductance model. This quantity, known as effective conductance, describes the total electric current flowing through an electric network and has a central role in homogenization theory. We establish a central limit theorem for the effective conductance under the assumptions of Dirichlet boundary conditions and conductances with small ellipticity contrast.

Die Arbeit beschäftigt sich insbesondere mit den Zusammenhängen zwischen Block-Faktorisierungs-Verfahren und algebraischen Mehrgitterverfahren. Dies führt auf neue Konvergenzresultate unter der Verwendung der CBS Konstanten. Des Weiteren wird eine Verallgemeinerung des AMGr-Verfahrens vorgestellt. Die Arbeit zeigt die wichtigsten Ergebnisse der heutigen Zeit von algebraischen Mehrgitterverfahren und der Verwendung von F-Glättern auf, dient aber auch als gutes Hilfsmittel für neue Interessenten algebraische Mehrgitterverfahren., In the thesis a special relation between block factorization methods and algebraic multigrid methods is used to proof new convergence results. An important tool is given by the CBS constant. Further a generalization of the AMGr method is introduced.

We formulate the static mechanical coupling of a geometrically exact Cosserat rod to a nonlinearly elastic continuum. In this setting, appropriate coupling conditions have to connect a one-dimensional model with director variables to a three-dimensional model without directors. Two alternative coupling conditions are proposed, which correspond to two different configuration trace spaces. For both, we show existence of solutions of the coupled problems, using the direct method of the calculus of variations. From the first-order optimality conditions, we also derive the corresponding conditions for the dual variables. These are then interpreted in mechanical terms.

We consider a generalization of the Connected Facility Location problem where clients may connect to open facilities via access trees shared by multiple clients. The task is to choose facilities to open, to connect these facilities by a core Steiner tree (of infinite capacity), and to design and dimension the access trees, such that the capacities installed on the edges of these trees suffice to simultaneously route all clients' demands to the open facilities. We assume that the available edge capacities are given by a set of different cable types whose costs obey economies of scale. The objective is to minimize the total cost of opening facilities, building the core Steiner tree among them, and installing capacities on the access tree edges. In this paper, we devise the first constant-factor approximation algorithm for this problem. We also present a factor 6.72 approximation algorithm for a simplified version of the problem where multiples of only one single cable type can be installed on the access edges.

We examine when a matrix whose elements are differentiable functions in one variable commutes with its derivative. This problem was discussed in a letter from Issai Schur to Helmut Wielandt written in 1934, which we found in Wielandt's Nachlass. We present this letter and its translation into English. The topic was rediscovered later and partial results were proved. However, there are many subtle observations in Schur's letter which were not obtained in later years. Using an algebraic setting, we put these into perspective and extend them in several directions. We present in detail the relationship between several conditions mentioned in Schur's letter and we focus in particular on the characterization of matrices called Type 1 by Schur. We present several examples that demonstrate Schur's observations.