### Refine

#### Document Type

- ZIB-Report (8)
- Article (4)
- In Proceedings (2)
- Master's Thesis (1)

#### Keywords

- Markov State Models (2)
- Mixed-Integer Programming (2)
- NESS (2)
- Non-reversible Markov Processes (2)
- Covering (1)
- Factors (1)
- Hall condition (1)
- Hall's Theorem (1)
- König's Theorem (1)
- Matchings in hypergraphs (1)

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})$.

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.

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.

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.

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.