TY - GEN A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf T1 - An Approximation Result for Matchings in Partitioned Hypergraphs 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})$. T3 - ZIB-Report - 14-30 Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-51083 ER - TY - GEN A1 - Beckenbach, Isabel T1 - A Hypergraph Network Simplex Algorithm 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. T3 - ZIB-Report - 17-36 Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64539 SN - 1438-0064 ER - 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 - GEN A1 - Beckenbach, Isabel A1 - Peis, Britta A1 - Schaudt, Oliver A1 - Scheidweiler, Robert T1 - A Combinatorial Proof of a König-type Theorem for Unimodular Hypergraphs N2 - We state purely combinatorial proofs for Kö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. T3 - ZIB-Report - 17-27 KW - Packing KW - Covering KW - Total Unimodularity KW - König's Theorem KW - Factors Y1 - 2017 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-64017 SN - 1438-0064 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Scheidweiler, Robert T1 - Perfect f-Matchings and f-Factors in Hypergraphs - A Combinatorial Approach 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. T3 - ZIB-Report - 16-22 KW - perfect f-matchings in hypergraphs KW - f-factors in hypergraphs KW - mengerian hypergraph KW - balanced hypergraph KW - perfect hypergraph KW - Hall's Theorem Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-59071 SN - 1438-0064 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf A1 - Knoben, Loes A1 - Kretz, David A1 - Uetz, Marc T1 - The S-Bahn Challenge in Berlin N2 - 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. T3 - ZIB-Report - 15-13 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-53792 UR - https://gor.uni-paderborn.de/index.php?id=362 SN - 1438-0064 ER - TY - THES A1 - Beckenbach, Isabel T1 - Special cases of the hypergraph assignment problem N2 - 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. Y1 - 2013 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-42480 ER - TY - GEN A1 - Beckenbach, Isabel A1 - Hatzel, Meike A1 - Wiederrecht, Sebastian T1 - The Tight Cut Decomposition of Matching Covered Uniformable Hypergraphs N2 - 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á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á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. T3 - ZIB-Report - 18-61 KW - uniform hypergraphs KW - perfect matchings KW - tight cuts Y1 - 2018 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-71149 SN - 1438-0064 ER -