最大并行流问题  

Max Concurrent Flow Problem

作　　者：董丽薇[1] 赵大宇[1] 

机构地区：[1]沈阳师范大学数学与系统科学学院,辽宁沈阳110034

出　　处：《沈阳师范大学学报（自然科学版）》2007年第1期1-4,共4页Journal of Shenyang Normal University:Natural Science Edition

基　　金：辽宁省高等学校科学研究项目(202112020);知识科学与知识管理研究资助项目(027)

摘　　要：研究了Fleischer.L给出的求解最大并行流问题的一个近似算法,其求出的目标函数值为λ≥(1-ε)3OPT.对其算法进行了改进,给出了λ≥1/(1+3ε)OPT的最大并行流全多项式近似算法.最后给出数值例子,验证了算法的有效性.We present the fully polynomial approxirnation schemes for max concurrent flow problem for λ≥ 1/（ 1 ＋ 3 ε ） OPT, through modifying of the algorithm with objective function value of λ≥ （ 1- ε ）^3 OPT by Fleischer. L. Finally, an .numerical example is given to illustrate that our algorithm is effective.

关 键 词：最大并行流问题 全多项式时间近似算法 算法复杂性 

分 类 号：O221.7[理学—运筹学与控制论] O157.5[理学—数学]