一个局部带优先权的最大多物资网络流问题

给出一个局部带优先权的最大多物资网络流问题(MMFP-LPRI),证明它的解存在,并给出其η-松弛解的定义.通过做辅助网络,并运用程丛电等根据Korte和Vygen于2000年在Young,Garg和K(o|¨)nemann等工作的基础上给出的求最大多种物资网络流问题的ε-近似解的多项式方案设计的一个算法作为子程序进行二分收索建立了一个求所给问题的η-松弛解的拟多项式算法.最后,进行算法分析,证明了所设计的算法的输出结果确实是MMFP-LPRT的一个η-松弛解.

A Maximum Multicommodity Flow Problem with Local Priority

We present a maximum multicommodity flow problem with local priority(MMFPLPRI),and prove the existence of its solutions.Moreover,we also propose the definition of η-relax solutions for the problem presented.By constructing the auxiliary network,and through implementing two partition search using the subprogram that designed by Cheng Cong-dian et al.basing on the multicommodity flow approximation scheme provided by Korte and Vygen(2000) from the works of Garg and Konemann(1998),Young(1995) and others for the approximation algorithm on Maximum Multicommodity Flow Problems,we design a pseudopolynomial algorithm to obtain the η-relax solution of MMFP-LPRI.Finally,we analyze the complexity of the algorithm and prove that the output of the algorithm designed is indeed an η-relax solution of MMFP-LPRI.