Academic Journals Database
Disseminating quality controlled scientific knowledge

Stable Multicommodity Flows

ADD TO MY LIST
 
Author(s): Tamás Király | Júlia Pap

Journal: Algorithms
ISSN 1999-4893

Volume: 6;
Issue: 1;
Start page: 161;
Date: 2013;
Original page

Keywords: stable matching problem | stable flows | multicommodity flows | PPAD-completeness | Sperner’s Lemma

ABSTRACT
We extend the stable flow model of Fleiner to multicommodity flows. In addition to the preference lists of agents on trading partners for each commodity, every trading pair has a preference list on the commodities that the seller can sell to the buyer. A blocking walk (with respect to a certain commodity) may include saturated arcs, provided that a positive amount of less preferred commodity is traded along the arc. We prove that a stable multicommodity flow always exists, although it is PPAD-hard to find one.
RPA Switzerland

RPA Switzerland

Robotic process automation

    

Tango Jona
Tangokurs Rapperswil-Jona