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

 

Abstract:
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

 

Abstract:
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 USA Payday Loans you don't have to seek the help of relatives or go to a bank. If you have already decided to take Levitra, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.