Stable multicommodity flows

DOI10.3390/A6010161MaRDI QIDQ1736550zbMATH OpenOpenAlexFDO

Authors Tamás Király, Júlia Pap

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a6010161

zbMATH Keywords

multicommodity flowsPPAD-completenessSperner's lemmastable flowsstable matching problem

Mathematics Subject Classification ID

Flows in graphs (05C21) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Deterministic network models in operations research (90B10) Matching models (91B68)

Review text

Summary: 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.

Recommendations

• On stable matchings and flows
• On stable matchings and flows
• scientific article; zbMATH DE number 3914038

Cites work

• A note on kernels and Sperner's Lemma
• On stable matchings and flows
• Reducibility among Fractional Stability Problems
• Stable flows over time
• The Stable Allocation (or Ordinal Transportation) Problem

Cited in

(6)

• Editorial: Special issue on matching under preferences
• On the complexity of stable hypergraph matching, stable multicommodity flow and related problems
• Online Multi-Commodity Flow with High Demands
• On stable matchings and flows
• scientific article; zbMATH DE number 3914038 (Why is no real title available?)
• The Klein bottle and multicommodity flows

This page was built for publication: Stable multicommodity flows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736550)