SwePub
Sök i LIBRIS databas

  Utökad sökning

(WFRF:(Hessler Martin)) pers:(Wästlund Johan)
 

Sökning: (WFRF:(Hessler Martin)) pers:(Wästlund Johan) > The polymatroid ass...

The polymatroid assignment problem

Hessler, Martin, 1979- (författare)
Linköpings universitet,Tillämpad matematik,Tekniska högskolan
Wästlund, Johan (författare)
Linköpings universitet,Tillämpad matematik,Tekniska högskolan
 (creator_code:org_t)
Engelska.
  • Annan publikation (övrigt vetenskapligt/konstnärligt)
Abstract Ämnesord
Stäng  
  • 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.

Ämnesord

NATURVETENSKAP  -- Matematik (hsv//swe)
NATURAL SCIENCES  -- Mathematics (hsv//eng)

Nyckelord

MATHEMATICS
MATEMATIK

Publikations- och innehållstyp

vet (ämneskategori)
ovr (ämneskategori)

Till lärosätets databas

Hitta mer i SwePub

Av författaren/redakt...
Hessler, Martin, ...
Wästlund, Johan
Om ämnet
NATURVETENSKAP
NATURVETENSKAP
och Matematik
Av lärosätet
Linköpings universitet

Sök utanför SwePub

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy