Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 3 of 17
Back to Result List

Special cases of the hypergraph assignment problem

Please always quote using this URN: urn:nbn:de:0297-zib-42480
  • 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.

Download full text files

Export metadata

Metadaten
Author:Isabel BeckenbachORCiD
Document Type:Master's Thesis
Granting Institution:Technische Universität Berlin
Advisor:Martin Grötschel, Ralf Borndörfer
Date of final exam:2013/03/01
Publishing Institution:Zuse Institute Berlin (ZIB)
Date of first Publication:2013/09/16
Page Number:87
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.