Publikationen am Institut für Mathematik

Anzahl der Treffer: 2072
Erstellt: Wed, 27 Mar 2024 23:21:46 +0100 in 0.0888 sec


Espuny Díaz, Alberto; Morris, Patrick; Perarnau, Guillem; Serra, Oriol
Speeding up random walk mixing by starting from a uniform vertex. - In: Electronic journal of probability, ISSN 1083-6489, Bd. 29 (2024), 26, S. 1-25

The theory of rapid mixing random walks plays a fundamental role in the study of modern randomised algorithms. Usually, the mixing time is measured with respect to the worst initial position. It is well known that the presence of bottlenecks in a graph hampers mixing and, in particular, starting inside a small bottleneck significantly slows down the diffusion of the walk in the first steps of the process. The average mixing time is defined to be the mixing time starting at a uniformly random vertex and hence is not sensitive to the slow diffusion caused by these bottlenecks. In this paper we provide a general framework to show logarithmic average mixing time for random walks on graphs with small bottlenecks. The framework is especially effective on certain families of random graphs with heterogeneous properties. We demonstrate its applicability on two random models for which the mixing time was known to be of order (log n)2, speeding up the mixing to order logn. First, in the context of smoothed analysis on connected graphs, we show logarithmic average mixing time for randomly perturbed graphs of bounded degeneracy. A particular instance is the Newman-Watts small-world model. Second, we show logarithmic average mixing time for supercritically percolated expander graphs. When the host graph is complete, this application gives an alternative proof that the average mixing time of the giant component in the supercritical Erd˝os-Rényi graph is logarithmic.



https://doi.org/10.1214/24-EJP1091
Bartel, Andreas; Clemens, Markus; Günther, Michael; Jacob, Birgit; Reis, Timo
Port-Hamiltonian systems’ modelling in electrical engineering. - In: Scientific computing in electrical engineering, (2024), S. 133-143

The port-Hamiltonian (pH) modelling framework allows for models that preserve essential physical properties such as energy conservation or dissipative inequalities. If all subsystems are modelled as pH systems and the inputs are related to the output in a linear manner, the overall system can be modelled as a pH system, too, which preserves the properties of the underlying subsystems. If the coupling is given by a skew-symmetric matrix, as usual in many applications, the overall system can be easily derived from the subsystems without the need of introducing dummy variables and therefore artificially increasing the complexity of the system. Hence the framework of pH systems is especially suitable for modelling multiphysical systems.



https://doi.org/10.1007/978-3-031-54517-7_15
âCurgus, Branko; Derkach, Volodymyr; Trunk, Carsten
Indefinite Sturm-Liouville operators in polar form. - In: Integral equations and operator theory, ISSN 1420-8989, Bd. 96 (2024), 2, S. 1-58

https://doi.org/10.1007/s00020-023-02746-3
Heri, Sebastian; Lieb, Julia; Rosenthal, Joachim
Self-dual convolutional codes. - In: IEEE transactions on information theory, Bd. 70 (2024), 2, S. 950-963

This paper investigates the concept of self-dual convolutional codes. We derive the basic properties of this interesting class of codes and we show how some of the techniques to construct self-dual linear block codes generalize to self-dual convolutional codes. As for self-dual linear block codes we are able to give a complete classification for some small parameters.



https://doi.org/10.1109/TIT.2023.3343108
Eichfelder, Gabriele; Quintana, Ernest
Set-based robust optimization of uncertain multiobjective problems via epigraphical reformulations. - In: European journal of operational research, ISSN 0377-2217, Bd. 313 (2024), 3, S. 871-882

In this paper, we study a method for finding robust solutions to multiobjective optimization problems under uncertainty. We follow the set-based minmax approach for handling the uncertainties which leads to a certain set optimization problem with the strict upper type set relation. We introduce, under some assumptions, a reformulation using instead the strict lower type set relation without sacrificing the compactness property of the image sets. This allows to apply vectorization results to characterize the optimal solutions of these set optimization problems as optimal solutions of a multiobjective optimization problem. We end up with multiobjective semi-infinite problems which can then be studied with classical techniques from the literature.



https://www.sciencedirect.com/science/article/pii/S0377221723007208/pdfft?md5=f5272f8643b0ce953294091001149d0f&pid=1-s2.0-S0377221723007208-main.pdf
Böhme, Thomas; Harant, Jochen; Kriesell, Matthias; Mohr, Samuel; Schmidt, Jens M.
Rooted minors and locally spanning subgraphs. - In: Journal of graph theory, ISSN 1097-0118, Bd. 105 (2024), 2, S. 209-229

Results on the existence of various types of spanning subgraphs of graphs are milestones in structural graph theory and have been diversified in several directions. In the present paper, we consider “local” versions of such statements. In 1966, for instance, D. W. Barnette proved that a 3-connected planar graph contains a spanning tree of maximum degree at most 3. A local translation of this statement is that if G is a planar graph, X is a subset of specified vertices of G such that X cannot be separated in G by removing two or fewer vertices of G, then G has a tree of maximum degree at most 3 containing all vertices of X. Our results constitute a general machinery for strengthening statements about k-connected graphs (for 1 ≤ k ≤ 4) to locally spanning versions, that is, subgraphs containing a set X ⊆ V (G) of a (not necessarily planar) graph G in which only X has high connectedness. Given a graph G and X ⊆ V (G), we say M is a minor of G rooted at X, if M is a minor of G such that each bag of M contains at most one vertex of X and X is a subset of the union of all bags. We show that G has a highly connected minor rooted at X if X ⊆ V (G) cannot be separated in G by removing a few vertices of G. Combining these investigations and the theory of Tutte paths in the planar case yields locally spanning versions of six well-known results about degree-bounded trees, Hamiltonian paths and cycles, and 2-connected subgraphs of graphs.



https://doi.org/10.1002/jgt.23012
Beddig, Rebekka S.; Benner, Peter; Dorschky, Ines; Reis, Timo; Schwerdtner, Paul; Voigt, Matthias; Werner, Steffen W. R.
Structure-preserving model reduction for dissipative mechanical systems. - In: Calm, smooth and smart, (2024), S. 209-230

Suppressing vibrations in mechanical systems, usually described by second-order dynamical models, is a challenging task in mechanical engineering in terms of computational resources even nowadays. One remedy is structure-preserving model order reduction to construct easy-to-evaluate surrogates for the original dynamical system having the same structure. In our work, we present an overview of recently developed structure-preserving model reduction methods for second-order systems. These methods are based on modal and balanced truncation in different variants, as well as on rational interpolation. Numerical examples are used to illustrate the effectiveness of all described methods.



https://doi.org/10.1007/978-3-031-36143-2_11
Espuny Díaz, Alberto; Janzer, Barnabás; Kronenberg, Gal; Lada, Joanna
Long running times for hypergraph bootstrap percolation. - In: European journal of combinatorics, Bd. 115 (2024), 103783, S. 1-18

Consider the hypergraph bootstrap percolation process in which, given a fixed r-uniform hypergraph H and starting with a given hypergraph G0, at each step we add to G0 all edges that create a new copy of H. We are interested in maximising the number of steps that this process takes before it stabilises. For the case where H = Kr+1(r) with r ≥ 3, we provide a new construction for G0 that shows that the number of steps of this process can be of order Θ (nr). This answers a recent question of Noel and Ranganathan. To demonstrate that different running times can occur, we also prove that, if H is K4(3) minus an edge, then the maximum possible running time is 2n − ⌊log2(n−2)⌋ − 6. However, if H is K5(3) minus an edge, then the process can run for Θ (n3) steps.



https://doi.org/10.1016/j.ejc.2023.103783
Eichfelder, Gabriele; Stein, Oliver
Limit sets in global multiobjective optimization. - In: Optimization, ISSN 1029-4945, Bd. 73 (2024), 1, S. 1-27

Inspired by the recently introduced branch-and-bound method for continuous multiobjective optimization problems from G. Eichfelder, P. Kirst, L. Meng, O. Stein [A general branch-and-bound framework for continuous global multiobjective optimization. J Glob Optim. 2021;80:195-227], we study for a general class of branch-and-bound methods in which sense the generated terminal enclosure and the terminal provisional nondominated set approximate the nondominated set when the termination accuracy is driven to zero. Our convergence analysis of the enclosures relies on constructions from the above paper, but is self-contained and also covers the mixed-integer case. The analysis for the provisional nondominated set is based on general convergence properties of the epsilon-nondominated set, and hence it is also applicable to other algorithms which generate such points. Furthermore, we discuss post-processing steps for the terminal enclosure and provide numerical illustrations for the cases of two and three objective functions.



https://doi.org/10.1080/02331934.2022.2092479
Goor, Pieter; vanMahony, Robert; Schaller, Manuel; Worthmann, Karl
Reprojection methods for Koopman-based modelling and prediction. - In: IEEE Xplore digital library, ISSN 2473-2001, (2023), S. 315-321

Extended Dynamic Mode Decomposition (eDMD) is a powerful tool to generate data-driven surrogate models for the prediction and control of nonlinear dynamical systems in the Koopman framework. In eDMD a compression of the lifted system dynamics on the space spanned by finitely many observables is computed, in which the original space is embedded as a low-dimensional manifold. While this manifold is invariant for the infinite-dimensional Koopman operator, this invariance is typically not preserved for its eDMD-based approximation. Hence, an additional (re-)projection step is often tacitly incorporated to improve the prediction capability. We propose a novel framework for consistent reprojectors respecting the underlying manifold structure. Further, we present a new geometric reprojector based on maximum-likelihood arguments, which significantly enhances the approximation accuracy and preserves known finite-data error bounds.



https://doi.org/10.1109/CDC49753.2023.10383796