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.


  To apply for Payday Loans In United States you don't have to seek the help of relatives or go to a bank. But at the same time, it acts only with sexual arousal. Cheap Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.