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

摘要：

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

关键词：双标准、多种物资网络流、算法、复杂性、逼近关系.

所属期刊栏目：35

分类号：O157;O221(代数、数论、组合理论)

资助基金：沈阳师范大学校科研和教改项目054-55440102005

在线出版日期：2008-07-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：170-174