The polymatroid assignment problem

• In 1998 G. Parisi published the two page note, with the conjecturedexact formula for the random bipartite matching (or assignment) problemwith exponential edge costs. This formula was subsequently proved and generalized in different directions. One such generalization given in was called the flow problem. Here we take the generalization process one step further. In a two-dimensional urn-processwas developed in order to calculate all moments of the cost of the flow problem. This process is here generalized to a larger class of optimization problems on the bipartite graph. These problems are defined by assigning a polymatroid structure to each of the two sets of vertices. An edge set isa feasible solution to the optimization problem if the two associated vertex(multi-)sets are both independent. Our main theorem states that the moments of the cost of the polymatroid assignment problem are characterizedby the associated urn process. We apply this theorem to some concrete problems which are not covered by previously known generalization of the bipartite matching problem.

Subject headings

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Keyword

MATHEMATICS

MATEMATIK

Publication and Content Type

vet (subject category)

ovr (subject category)