## 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

## New Discoveries of Domination between Traffic Matrices

A traffic matrix $D_1$ dominates a traffic matrix $D_2$ if any capacity reservation supporting $D_1$ supports $D_2$ as well. We prove that $D_3$ dominates $D_3+ \lambda(D_2-D_1)$ for any $\lambda\geq 0$ if $D_1$ dominates $D_2$. By the property , it is pointed out that the domains supported by different traffic matrices are isomorphic on the extended … Read more