Pengfei Liu 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
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 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