Improvements on the proof of an approximate scheme for the maximum multicommodity flow problem

摘要：

To approximately solve the maximum multicom modity flow problem has been attacked since the 50 years of last century. In 2000, according to the framework of Garg and K(o)nernann, Korte and Vygen presented a scheme for the problem, and showed that it was a full polynomial time approx imation scheme (FPTAS) to find the ε-approximate solutions of the maximum multicommodity flow problem. The present work improves the described contributions of Korte and Vygen.

关键词： network multicommodity flow algorithm

作者: Congdian Cheng Zhenpeng Li

作者单位: College of Mathematics and Systems Science Shenyang Normal University Shenyang, 110034, Peoples Rep Institute of Systems Science Academy of Mathematics and Systems Science Chinese Academy of Sciences

会议类型: 国际会议

会议名称: 2010 4th International Conference on Intelligent Information Techonlogy Application(第四届智能信息技术应用国际学术研讨会 IITA 2010)

会议地点: 秦皇岛

会议语种:英文

页码: 311-314

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