期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

最大一致流问题的一个逼近算法 被引量：1

An Approximation Scheme of Maximum Concurrent Flow Problem
下载PDF
导出
摘要 通过建构辅助网络,以Korte和Vygen于2000年所给出的一个求最大多种物资网络流问题的逼近解的完全多项式算法作为子程序进行二分搜索,给出了一个新的求解最大一致流问题的逼近算法.然后,进行算法分析,说明了所建立的算法是拟多项式算法,并且给出与证明了一个有关输出的流与输入问题的解之间的逼近关系.该项工作表明从一个多种物资网络流问题的算法出发通过变换求解其他有关问题是可行的,并且为研究网络流问题提供了一种新的方法. Via constructing the auxiliary for the Maximum Concurrent Flow Problem network, a new approximation algorithm is proposed and studied through implementing binary searching with the Multicommodity Flow Approximation Scheme provided by Korte and Vygen （2000）. Making the algorithm analysis, explain the designed algorithm is a pseudopolynomial algorithm, propose and prove an approximation relation between the solution of input problem and the output flow. Our work shows it is feasible that via a certain transformation, a multicommodity flow problem can be solved from a scheme of another related problem. In addition, the present work also proposes an new clue to this research line.
作者 郭海旭 程丛电 吴亚坤
机构地区 辽宁大学计算中心 沈阳师范大学数学与系统科学学院
出处 《辽宁大学学报（自然科学版）》 CAS 2009年第1期35-39,共5页 Journal of Liaoning University：Natural Sciences Edition
关键词 多物资网络流 逼近 算法 复杂性 bicriteria network multicommodity flow approximation scheme complexity approximationrelation.
分类号 O157 [理学—基础数学] O221 [理学—运筹学与控制论]
  • 相关文献

参考文献14

  • 1Biswas J, Matual D W. The two - flow routing algorithms for the maximum concurrent flow problem [ A ]. In Proceedings of the ACM Fall Joint Conference, ACM, New York, 1986:629-635.
  • 2FLEISCHER L K. Approximating frcational multicom-modity flow independent of the number of commodities [J]. SIAM J Discrete Math, 2000,13(4) :505 -520 (electronic).
  • 3Garg N, Kφnemann J. Faster and simpler algorithms for muhicommodity flow and other fractional packing problems[A]. Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science [ C ]. 1998 : 300 - 309.
  • 4LEIGHTON T, MAKEDON F, PLOTKIN S, et al. Fast approximation algorithms for muhicommodity flow problems[J]. J Comput Syst Sci 50, 1995:228 - 243.
  • 5RADZIK T. Fast deterministic approximation for the multicommodity flow problem [ J ]. Math Program, 1997, 78:43 -58.
  • 6Shahrokhi F, Matula D W. On solving large maximum concurrent flow problems [ C ]. In Proceedings of the ACM Computer Conference, ACM, New York, 1987 : 205 - 209.
  • 7Shahrokhi F, Matula D W. The maximum concurrent flow problem[J]. J ACM 1990,37:318 -334.
  • 8Thompson B, Matula D W. A flow rerouting algorithm for the maximum concurrent flow problem With varia- ble capacities and demands, and its applications to cluster analysis[ R]. Technical Report 85 - Cse - 12, Dept. of Computer Science and Engineering, Southern Methodist Univ. , 1986.
  • 9程丛电,唐恒永,赵传立.一个多物资网络流问题的逼近算法[J].辽宁大学学报（自然科学版）,2008,35(2):170-174. 被引量：4
  • 10Young N. Randomized rounding without solving the linear program [ A ]. Proceedings of the 6th Annual ACM- SIAM Symposium on Discrete Algorithms [C]. 1995:170 - 178.

二级参考文献4

  • 1Ford L R, Fulkerson D R. A suggested computation for maximal multicommodity network flows [ J ]. Management Science, 1958, 5 : 91 - 101.
  • 2Korte B, Vygen J. Combinatorial Optimization Theory and Algorthms[ M]. Springer - Verlag, Berlin, 2000.
  • 3Young N. Randomized rounding without solving the linear program [ A ]. Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms[ C]. 1995 : 170 - 178.
  • 4Garg N, Konemann J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems[A]. Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science[ C ]. 1998 : 300 - 309.

共引文献3

同被引文献8

  • 1Ford L R, Fulkerson D R. A suggested computation for maximal multicommodity network flows [ J ]. Management Science, 1958, 5 : 91 - 101.
  • 2Cheng C D, Tang H Y, Zhao C L. Approximation algorithm for a bicriteria muhicommodity flow problem [ C ]. Proceedings of 2008 IEEE International Conference on Service Operations and Logistics, and Infor- matics, 2008 : 1756 - 1760.
  • 3Korte B, Vygen J. Combinatorial Optimization Theory and Algorthms[ M]. Springer - Verlag, Berlin,2000.
  • 4Young N. Randomized rounding without solving the linear program [ C ]. Proceedings of the 6th Annual ACM -SIAM Symposium on Discrete Algorithms, 1995 : 170 - 178.
  • 5Garg N, Konemann J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems [ C ]. Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Seienee, 1998 : 300 -309.
  • 6Coudert D, Rivano H, Roche X. A combinatorial approximation algorithm for the muhieommodity flow problem [ J ]. Approximation and online algorithms lecture notes in computer Science, 2004, 2909:256 - 259.
  • 7Cheng C D. Two kinds of generalized network flow with node formula [ C ]. Proceedings 2009 IEEE International Conference on Service Intelligent Computing and Intelligent Systems, Vol. 1,2009 : 425 -428.
  • 8程丛电,唐恒永,赵传立.一个多物资网络流问题的逼近算法[J].辽宁大学学报（自然科学版）,2008,35(2):170-174. 被引量：4

引证文献1

辽宁大学学报（自然科学版）
2009年 第1期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部