广义最大并行流算法的改进  

Generalized Maximum Concurrent Flow Problem

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

机构地区：[1]沈阳师范大学,沈阳110034

出　　处：《系统管理学报》2007年第6期678-684,共7页Journal of Systems & Management

基　　金：国家自然科学基金资助项目(10471096)

摘　　要：研究了Karakostas G给出的求解最大并行流问题的一个近似算法,将其算法的参数进行了改进,给出了算法的时间复杂性不依赖于物资数k的广义最大并行流的全多项式时间近似算法,该算法只适用于广义的lossy网络。用改进后算法求出的目标函数值更接近于最优值,对该近似算法的近似性和算法的时间复杂性进行了证明。最后,用C语言编程,计算数值例子,通过对比充分验证了改进后算法的正确性和有效性。In this paper, we discuss the algorithm of maximum concurrent flow problem given by Karakostas G, modify the parameter of it, apply it and present fully polynomial approximation schemes for generalized maximum concurrent flow problem that run in time independent of the number of commodities k. The algorithm is only suitable for lossy network. The objective function value of the new algorithm is closer to exam optimal to optimal value. We give the proof of approximation and complexity. Finally, a numerical pie is given by c programming to illustrate that our algorithm is valid and effective.

关 键 词：广义最大并行流 全多项式时间近似算法 算法复杂性 lossy网络 获得因子 广义的最短路 

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