一个多物资网络流问题的逼近算法

给出最小满意率最大双标准最大多物资网络流问题,并证明其解存在.建构辅助网络,运用Korte和Vygen于2000年在Young,Garg和Kφnemann等工作的基础上给出的求最大多种物资网络流问题的ε—逼近解的完全多项式算法作子程序和二分收索方法做出一个求所给问题的解的拟多项式逼近算法.分析算法的复杂性,给出并证明算法的逼近程度.

多物资网络流问题的一个注记

给出几个新的多物资网络流问题,证明它们的解存在,并提出需要近一步研究的有关问题.

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

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