Faster Approximation Algorithm for Generalized Maximum Concurrent Flow Problem with Budget Constraint

摘要：

We present fully polynomial approximation algorithm for generalized maximum concurrent flow problem with budget constraint that run in time independent of the number of commodities k.We show that by modifying the algorithms by Karakostas and Fleischer.We can reduce their running time.At the same time the approximation solution of the new algorithm is closer to optimal value.

关键词： generalized concurrent flow gain factor fully polynomial approximation algorithm complexity of algorithm lossy network budget constraint

作者: Liwei Dong Liying Bian Hengyong Tang

作者单位: Shenyang normal university College of softwareChina,Shenyang 110034 Shenyang normal university College of Maths and Systematic Science China,Shenyang 110034

会议类型: 国际会议

会议名称: 2008 IEEE International Conference on Service Operations and Logistics, and Informatics(IEEE/SOLI’2008)(IEEE服务运作、物流与信息年会)

会议地点: 北京

会议语种:英文

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