Monday, 15:45 - 16:10 h, Room: H 3021


Tamás Király
Multiplayer multicommodity flows

Coauthors: Attila Bernáth, Mádi-Nagy Gergely, Pap Gyula, Pap Júlia


We investigate the Multiplayer Multicommodity Flow Problem, a version of the multicommodity flow problem where players have different subnetworks and commodities over a common node set. Pairs of players have contracts where one of them agrees to route the flow of the other player (up to a given capacity) between two specified nodes. In return, the second player pays an amount proportional to the flow value.
We show that the social optimum can be computed by linear programming. In contrast, an equilibrium solution, although it always exists under some natural conditions, is PPAD-hard to find. We analyze hardness in relation to the structure of the digraph formed by the contracts between players, and prove that an equilibrium can be found in polynomial time if every strongly connected component of this digraph is a cycle.


Talk 2 of the invited session Mon.3.H 3021
"Equilibria and combinatorial structures" [...]
Cluster 2
"Combinatorial optimization" [...]


  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 For Sale, be sure to consult a doctor, you don't have any contraindications and act strictly due to a prescription.