A Combinatorial Algorithm for the Multi-commodity Flow Problem

This paper researches combinatorial algorithms for the multi-commodity flow problem. We relax the capacity constraints and introduce a \emph{penalty function} $$h$$ for each arc. If the flow exceeds the capacity on arc $$a$$, arc $$a$$ would have a penalty cost. Based on the \emph{penalty function} $$h$$, a new conception , \emph{equilibrium pseudo-flow}, is introduced. Then … Read more

A Combinatorial Algorithm for the Multi-commodity Flow Problem

This paper researches combinatorial algorithms for the multi-commodity flow problem. We relax the capacity constraints and introduce a \emph{penalty function} $$h$$ for each arc. If the flow exceeds the capacity on arc $$a$$, arc $$a$$ would have a penalty cost. Based on the \emph{penalty function} $$h$$, a new conception , \emph{equilibrium pseudo-flow}, is introduced. Then … Read more