Refine
Document Type
- ZIB-Report (8)
- Article (5)
- In Proceedings (2)
- Doctoral Thesis (1)
- Master's Thesis (1)
Is part of the Bibliography
- no (17)
Keywords
- Factors (2)
- Markov State Models (2)
- Mixed-Integer Programming (2)
- NESS (2)
- Non-reversible Markov Processes (2)
- Balanced Hypergraphs (1)
- Covering (1)
- Hall condition (1)
- Hall's Theorem (1)
- König's Theorem (1)
- Matchings (1)
- Matchings in hypergraphs (1)
- Mengerian Hypergraphs (1)
- Network Flows (1)
- Normal Hypergraphs (1)
- Normal hypergraphs (1)
- Packing (1)
- Tight Cuts (1)
- Total Unimodularity (1)
- balanced hypergraph (1)
- f-factors in hypergraphs (1)
- mengerian hypergraph (1)
- perfect f-matchings in hypergraphs (1)
- perfect hypergraph (1)
- perfect matchings (1)
- tight cuts (1)
- uniform hypergraphs (1)
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 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})$.
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})$.
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.
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.
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.
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.