@misc{BeckenbachBorndoerfer, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {An Approximation Result for Matchings in Partitioned Hypergraphs}, doi = {10.1007/978-3-319-28697-6_5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-51083}, abstract = {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})\$.}, language = {en} } @misc{Beckenbach, author = {Beckenbach, Isabel}, title = {A Hypergraph Network Simplex Algorithm}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64539}, abstract = {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{\`a} 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.}, language = {en} } @article{BeckenbachScheidweiler, author = {Beckenbach, Isabel and Scheidweiler, Robert}, title = {Perfect f-Matchings and f-Factors in Hypergraphs - A Combinatorial Approach}, series = {Discrete Mathematics}, volume = {340}, journal = {Discrete Mathematics}, number = {10}, doi = {10.1016/j.disc.2017.05.005}, pages = {2499 -- 2506}, abstract = {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.}, language = {de} } @article{BeckenbachBorndoerferKnobenetal., author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf and Knoben, Loes and Kretz, David and Uetz, Marc J.}, title = {The S-Bahn Challenge in Berlin}, series = {OR News}, journal = {OR News}, number = {53}, pages = {10 -- 14}, language = {en} } @inproceedings{BeckenbachBorndoerfer, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {An Approximation Result for Matchings in Partitioned Hypergraphs}, series = {Operations Research Proceedings 2014}, booktitle = {Operations Research Proceedings 2014}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-28697-6_5}, pages = {31 -- 36}, abstract = {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})\$.}, language = {en} } @misc{BeckenbachPeisSchaudtetal., author = {Beckenbach, Isabel and Peis, Britta and Schaudt, Oliver and Scheidweiler, Robert}, title = {A Combinatorial Proof of a K{\"o}nig-type Theorem for Unimodular Hypergraphs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64017}, abstract = {We state purely combinatorial proofs for K{\"o}nig- and Hall-type theorems for a wide class of combinatorial optimization problems. Our methods rely on relaxations of the matching and vertex cover problem and, moreover, on the strong coloring properties admitted by bipartite graphs and their generalizations.}, language = {en} } @misc{BeckenbachScheidweiler, author = {Beckenbach, Isabel and Scheidweiler, Robert}, title = {Perfect f-Matchings and f-Factors in Hypergraphs - A Combinatorial Approach}, issn = {1438-0064}, doi = {10.1016/j.disc.2017.05.005}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59071}, abstract = {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.}, language = {en} } @misc{BeckenbachBorndoerferKnobenetal., author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf and Knoben, Loes and Kretz, David and Uetz, Marc}, title = {The S-Bahn Challenge in Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53792}, abstract = {The S-Bahn Challenge in Berlin is a challenge in which one has to travel the entire S-Bahn network of Berlin in the shortest possible time. We explain how the problem can be modeled and solved mathematically. Furthermore, we report on our record attempt on January 10, 2015.}, language = {en} } @misc{Beckenbach, type = {Master Thesis}, author = {Beckenbach, Isabel}, title = {Special cases of the hypergraph assignment problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42480}, school = {Zuse Institute Berlin (ZIB)}, pages = {87}, abstract = {In this thesis we investigate the hyperassignment problem with a special focus on connections to the theory of hypergraphs, in particular balanced and normal hyper- graphs, as well as its relation to the Stable Set Problem. The main point is the investigation of the matching and perfect matching polytope for partitioned hypergraphs. Therefore, valid inequalities, facets, and the dimension of some polytopes are given. Furthermore, we show that the trivial LP-relaxation of the Hyperassignment Problem obtained by relaxing x_i ∈ {0, 1} by 0 ≤ x_i ≤ 1 has an arbitrarily large integrality gap, even after adding all clique inequalities. Whereas the integrality gap of the trivial LP-relaxation of the maximum weight matching problem for partitioned hypergraphs with maximum part size M is at most 2M - 1. Additionally, computational results for small partitioned hypergraphs of part size two are presented. Using symmetry it was possible to calculate all minimal fractional vertices of the fractional perfect matching polytope of partitioned hypergraphs with part size two having at most twelve vertices.}, language = {en} } @misc{BeckenbachHatzelWiederrecht, author = {Beckenbach, Isabel and Hatzel, Meike and Wiederrecht, Sebastian}, title = {The Tight Cut Decomposition of Matching Covered Uniformable Hypergraphs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71149}, abstract = {The perfect matching polytope, i.e. the convex hull of (incidence vectors of) perfect matchings of a graph is used in many combinatorial algorithms. Kotzig, Lov{\´a}sz and Plummer developed a decomposition theory for graphs with perfect matchings and their corresponding polytopes known as the tight cut decomposition which breaks down every graph into a number of indecomposable graphs, so called bricks. For many properties that are of interest on graphs with perfect matchings, including the description of the perfect matching polytope, it suffices to consider these bricks. A key result by Lov{\´a}sz on the tight cut decomposition is that the list of bricks obtained is the same independent of the choice of tight cuts made during the tight cut decomposition procedure. This implies that finding a tight cut decomposition is polynomial time equivalent to finding a single tight cut. We generalise the notions of a tight cut, a tight cut contraction and a tight cut decomposition to hypergraphs. By providing an example, we show that the outcome of the tight cut decomposition on general hypergraphs is no longer unique. However, we are able to prove that the uniqueness of the tight cut decomposition is preserved on a slight generalisation of uniform hypergraphs. Moreover, we show how the tight cut decomposition leads to a decomposition of the perfect matching polytope of uniformable hypergraphs and that the recognition problem for tight cuts in uniformable hypergraphs is polynomial time solvable.}, language = {en} } @phdthesis{Beckenbach2019, author = {Beckenbach, Isabel}, title = {Matchings and Flows in Hypergraphs}, year = {2019}, abstract = {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{\"o}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.}, language = {en} } @inproceedings{Beckenbach, author = {Beckenbach, Isabel}, title = {A Hypergraph Network Simplex Algorithm}, series = {Operations Research Proceedings 2017}, volume = {Operations Research Proceedings 2017}, booktitle = {Operations Research Proceedings 2017}, editor = {Kliewer, Natalia and Ehmke, Jan Fabian and Bornd{\"o}rfer, Ralf}, publisher = {Springer}, address = {Cham}, pages = {309 -- 316}, abstract = {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{\`a} 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.}, language = {en} } @article{BeckenbachBorndoerfer, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {Hall's and Kőnig's theorem in graphs and hypergraphs}, series = {Discrete Mathematics}, volume = {341}, journal = {Discrete Mathematics}, number = {10}, doi = {10.1016/j.disc.2018.06.013}, pages = {2753 -- 2761}, abstract = {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{\´a}ry graphs. Furthermore, we give a generalization of Hall's theorem to normal hypergraphs.}, language = {en} } @article{Beckenbach, author = {Beckenbach, Isabel}, title = {Von Graphen zu Hypergraphen}, series = {OR News}, journal = {OR News}, number = {70}, issn = {1437-2045}, language = {en} } @misc{WitzigBeckenbachEifleretal., author = {Witzig, Jakob and Beckenbach, Isabel and Eifler, Leon and Fackeldey, Konstantin and Gleixner, Ambros and Grever, Andreas and Weber, Marcus}, title = {Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes}, issn = {1438-0064}, doi = {10.1137/16M1091162}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60353}, abstract = {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.}, language = {en} } @article{WitzigBeckenbachEifleretal., author = {Witzig, Jakob and Beckenbach, Isabel and Eifler, Leon and Fackeldey, Konstantin and Gleixner, Ambros and Grever, Andreas and Weber, Marcus}, title = {Mixed-Integer Programming for Cycle Detection in Non-reversible Markov Processes}, series = {Multiscale Modeling and Simulation}, volume = {16}, journal = {Multiscale Modeling and Simulation}, number = {1}, issn = {1438-0064}, doi = {10.1137/16M1091162}, pages = {248 -- 265}, abstract = {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.}, language = {en} } @misc{BeckenbachBorndoerfer, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {A Hall Condition for Normal Hypergraphs}, issn = {1438-0064}, doi = {10.1016/j.disc.2018.06.013}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-56175}, abstract = {Conforti, Cornu{\´e}jols, Kapoor, and Vusković gave a Hall-type condition for the non-existence of a perfect matching in a balanced hypergraph. We generalize this result to the class of normal hypergraphs.}, language = {en} }