Contributed Session Wed.2.H 3013

Wednesday, 13:15 - 14:45 h, Room: H 3013

Cluster 2: Combinatorial optimization [...]

Assignment problems


Chair: Geir Dahl



Wednesday, 13:15 - 13:40 h, Room: H 3013, Talk 1

Geir Dahl
Generalized Birkhoff polytopes and majorization

Coauthor: Richard A. Brualdi


The notion of majorization plays an important role in matrix
theory and other mathematical areas, like combinatorics, probability and physics. The basic notion is an ordering of vectors according to their partial sums, but several extensions exist. The purpose of this talk is to give a (very) brief introduction to majorization theory and to present some recent work on a generalization of Birkhoff polytopes related to majorization. Recall that the Birkhoff polytope is the set of all doubly stochastic matrices of a fixed size (it also corresponds to the perfect matching polytope). Main results include a generalization of the Birkhoff - von Neumann theorem and a characterization of the faces of such generalized Birkhoff polytopes. This is joint work with Richard
A. Brualdi (University of Wisconsin).



Wednesday, 13:45 - 14:10 h, Room: H 3013, Talk 2

Olga Heismann
The hypergraph assignment problem

Coauthors: Ralf Borndörfer, Achim Hildenbrandt


The hypergraph assignment problem (HAP) generalizes the assignment problem on directed graphs to directed hypergraphs; it is motivated by railway scheduling applications. The HAP is NP-hard even for problems with small hyperarc sizes and hypergraphs with a special partitioned structure. We propose an integer programming approach to the HAP and investigate the associated polyhedron of feasible solutions. Further, we develop combinatorial procedures that provide heuristic approximation results.


  The best way to go for you to know the credible Payday Loans Michigan providers. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra Without Prescription influence on blood clots.