TY - JOUR A1 - Beckenbach, Isabel A1 - Scheidweiler, Robert T1 - Perfect f-Matchings and f-Factors in Hypergraphs - A Combinatorial Approach JF - Discrete Mathematics N2 - We prove characterizations of the existence of perfect f-matchings in uniform mengerian and perfect hypergraphs. Moreover, we investigate the f-factor problem in balanced hypergraphs. For uniform balanced hypergraphs we prove two existence theorems with purely combinatorial arguments, whereas for non-uniform balanced hypergraphs we show that the f-factor problem is NP-hard. Y1 - 2017 U6 - https://doi.org/10.1016/j.disc.2017.05.005 VL - 340 IS - 10 SP - 2499 EP - 2506 ER - TY - JOUR A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf A1 - Knoben, Loes A1 - Kretz, David A1 - Uetz, Marc J. T1 - The S-Bahn Challenge in Berlin JF - OR News Y1 - 2015 UR - https://gor.uni-paderborn.de/index.php?id=362 IS - 53 SP - 10 EP - 14 ER - TY - CHAP A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf T1 - An Approximation Result for Matchings in Partitioned Hypergraphs T2 - Operations Research Proceedings 2014 N2 - We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most $2\sqrt{d}$ for partitioned hypergraphs with parts of size $\leq d$. Furthermore, we show that this bound cannot be improved to $\mathcal{O}(d^{0.5-\epsilon})$. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-28697-6_5 SP - 31 EP - 36 PB - Springer International Publishing ER - TY - THES A1 - Beckenbach, Isabel T1 - Matchings and Flows in Hypergraphs N2 - In this dissertation, we study matchings and flows in hypergraphs using combinatorial methods. These two problems are among the best studied in the field of combinatorial optimization. As hypergraphs are a very general concept, not many results on graphs can be generalized to arbitrary hypergraphs. Therefore, we consider special classes of hypergraphs, which admit more structure, to transfer results from graph theory to hypergraph theory. In Chapter 2, we investigate the perfect matching problem on different classes of hypergraphs generalizing bipartite graphs. First, we give a polynomial time approximation algorithm for the maximum weight matching problem on so-called partitioned hypergraphs, whose approximation factor is best possible up to a constant. Afterwards, we look at the theorems of König and Hall and their relation. Our main result is a condition for the existence of perfect matchings in normal hypergraphs that generalizes Hall’s condition for bipartite graphs. In Chapter 3, we consider perfect f-matchings, f-factors, and (g,f)-matchings. We prove conditions for the existence of (g,f)-matchings in unimodular hypergraphs, perfect f-matchings in uniform Mengerian hypergraphs, and f-factors in uniform balanced hypergraphs. In addition, we give an overview about the complexity of the (g,f)-matching problem on different classes of hypergraphs generalizing bipartite graphs. In Chapter 4, we study the structure of hypergraphs that admit a perfect matching. We show that these hypergraphs can be decomposed along special cuts. For graphs it is known that the resulting decomposition is unique, which does not hold for hypergraphs in general. However, we prove the uniqueness of this decomposition (up to parallel hyperedges) for uniform hypergraphs. In Chapter 5, we investigate flows on directed hypergraphs, where we focus on graph-based directed hypergraphs, which means that every hyperarc is the union of a set of pairwise disjoint ordinary arcs. We define a residual network, which can be used to decide whether a given flow is optimal or not. Our main result in this chapter is an algorithm that computes a minimum cost flow on a graph-based directed hypergraph. This algorithm is a generalization of the network simplex algorithm. N2 - Diese Arbeit untersucht Matchings und Flüsse in Hypergraphen mit Hilfe kombinatorischer Methoden. In Graphen gehören diese Probleme zu den grundlegendsten der kombinatorischen Optimierung. Viele Resultate lassen sich nicht von Graphen auf Hypergraphen verallgemeinern, da Hypergraphen ein sehr abstraktes Konzept bilden. Daher schauen wir uns bestimmte Klassen von Hypergraphen an, die mehr Struktur besitzen, und nutzen diese aus um Resultate aus der Graphentheorie zu übertragen. In Kapitel 2 betrachten wir das perfekte Matchingproblem auf Klassen von „bipartiten“ Hypergraphen, wobei es verschiedene Möglichkeiten gibt den Begriff „bipartit“ auf Hypergraphen zu definieren. Für sogenannte partitionierte Hypergraphen geben wir einen polynomiellen Approximationsalgorithmus an, dessen Gütegarantie bis auf eine Konstante bestmöglich ist. Danach betrachten wir die Sätze von Konig und Hall und untersuchen deren Zusammenhang. Unser Hauptresultat ist eine Bedingung für die Existenz von perfekten Matchings auf normalen Hypergraphen, die Halls Bedingung für bipartite Graphen verallgemeinert. Als Verallgemeinerung von perfekten Matchings betrachten wir in Kapitel 3 perfekte f-Matchings, f-Faktoren und (g, f)-Matchings. Wir beweisen Bedingungen für die Existenz von (g, f)-Matchings auf unimodularen Hypergraphen, perfekten f-Matchings auf uniformen Mengerschen Hypergraphen und f-Faktoren auf uniformen balancierten Hypergraphen. Außerdem geben wir eine Übersicht über die Komplexität des (g, f)-Matchingproblems auf verschiedenen Klassen von Hypergraphen an, die bipartite Graphen verallgemeinern. In Kapitel 4 untersuchen wir die Struktur von Hypergraphen, die ein perfektes Matching besitzen. Wir zeigen, dass diese Hypergraphen entlang spezieller Schnitte zerlegt werden können. Für Graphen weiß man, dass die so erhaltene Zerlegung eindeutig ist, was im Allgemeinen für Hypergraphen nicht zutrifft. Wenn man jedoch uniforme Hypergraphen betrachtet, dann liefert jede Zerlegung die gleichen unzerlegbaren Hypergraphen bis auf parallele Hyperkanten. Kapitel 5 beschäftigt sich mit Flüssen in gerichteten Hypergraphen, wobei wir Hypergraphen betrachten, die auf gerichteten Graphen basieren. Das bedeutet, dass eine Hyperkante die Vereinigung einer Menge von disjunkten Kanten ist. Wir definieren ein Residualnetzwerk, mit dessen Hilfe man entscheiden kann, ob ein gegebener Fluss optimal ist. Unser Hauptresultat in diesem Kapitel ist ein Algorithmus, um einen Fluss minimaler Kosten zu finden, der den Netzwerksimplex verallgemeinert. KW - Matchings KW - Balanced Hypergraphs KW - Normal Hypergraphs KW - Mengerian Hypergraphs KW - Factors KW - Tight Cuts KW - Network Flows Y1 - 2019 UR - http://nbn-resolving.de/urn:nbn:de:kobv:188-refubium-24385-6 ER - TY - CHAP A1 - Beckenbach, Isabel ED - Kliewer, Natalia ED - Ehmke, Jan Fabian ED - Borndörfer, Ralf T1 - A Hypergraph Network Simplex Algorithm T2 - Operations Research Proceedings 2017 N2 - We describe a network simplex algorithm for the minimum cost flow problem on graph-based hypergraphs which are directed hypergraphs of a particular form occurring in railway rotation planning. The algorithm is based on work of Cambini, Gallo, and Scutellà who developed a hypergraphic generalization of the network simplex algorithm. Their main theoretical result is the characterization of basis matrices. We give a similar characterization for graph-based hypergraphs and show that some operations of the simplex algorithm can be done combinatorially by exploiting the underlying digraph structure. Y1 - 2018 VL - Operations Research Proceedings 2017 SP - 309 EP - 316 PB - Springer CY - Cham ER - TY - JOUR A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf T1 - Hall’s and Kőnig’s theorem in graphs and hypergraphs JF - Discrete Mathematics N2 - We investigate the relation between Hall’s theorem and Kőnig’s theorem in graphs and hypergraphs. In particular, we characterize the graphs satisfying a deficiency version of Hall’s theorem, thereby showing that this class strictly contains all Kőnig–Egerváry graphs. Furthermore, we give a generalization of Hall’s theorem to normal hypergraphs. Y1 - 2018 U6 - https://doi.org/10.1016/j.disc.2018.06.013 VL - 341 IS - 10 SP - 2753 EP - 2761 ER - TY - JOUR A1 - Beckenbach, Isabel T1 - Von Graphen zu Hypergraphen JF - OR News Y1 - 2020 SN - 1437-2045 IS - 70 ER - TY - JOUR A1 - Witzig, Jakob A1 - Beckenbach, Isabel A1 - Eifler, Leon A1 - Fackeldey, Konstantin A1 - Gleixner, Ambros A1 - Grever, Andreas A1 - Weber, Marcus T1 - Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes JF - Multiscale Modeling and Simulation N2 - In this paper, we present a new, optimization-based method to exhibit cyclic behavior in non-reversible stochastic processes. While our method is general, it is strongly motivated by discrete simulations of ordinary differential equations representing non-reversible biological processes, in particular molecular simulations. Here, the discrete time steps of the simulation are often very small compared to the time scale of interest, i.e., of the whole process. In this setting, the detection of a global cyclic behavior of the process becomes difficult because transitions between individual states may appear almost reversible on the small time scale of the simulation. We address this difficulty using a mixed-integer programming model that allows us to compute a cycle of clusters with maximum net flow, i.e., large forward and small backward probability. For a synthetic genetic regulatory network consisting of a ring-oscillator with three genes, we show that this approach can detect the most productive overall cycle, outperforming classical spectral analysis methods. Our method applies to general non-equilibrium steady state systems such as catalytic reactions, for which the objective value computes the effectiveness of the catalyst. KW - Markov State Models KW - NESS KW - Non-reversible Markov Processes KW - Mixed-Integer Programming Y1 - 2018 U6 - https://doi.org/10.1137/16M1091162 SN - 1438-0064 VL - 16 IS - 1 SP - 248 EP - 265 ER -