| 最大一致流问题的一个逼近算法 |
| |
| 引用本文： | 郭海旭,程丛电,吴亚坤. 最大一致流问题的一个逼近算法[J]. 辽宁大学学报(自然科学版), 2009, 36(1): 35-39 |
| |
| 作者姓名： | 郭海旭 程丛电 吴亚坤 |
| |
| 作者单位： | 1. 辽宁大学,计算中心,辽宁,沈阳,110036
2. 沈阳师范大学,数学与系统科学学院,辽宁,沈阳,110034 |
| |
| 摘 要： | 通过建构辅助网络，以K0ne和Vygen于2000年所给出的一个求最大多种物资网络流问题的逼近解的完全多项式算法作为子程序进行二分搜索，给出了一个新的求解最大一致流问题的逼近算法．然后，进行算法分析，说明了所建立的算法是拟多项式算法，并且给出与证明了一个有关输出的流与输入问题的解之间的逼近关系．该项工作表明从一个多种物资网络流问题的算法出发通过变换求解其他有关问题是可行的，并且为研究网络流问题提供了一种新的方法．
|
| 关 键 词： | 多物资网络流 逼近 算法 复杂性 |
An Approximation Scheme of Maximum Concurrent Flow Problem |
| |
| GUO Hai-xu,CHENG Cong-dian,WU Ya-kun. An Approximation Scheme of Maximum Concurrent Flow Problem[J]. Journal of Liaoning University(Natural Sciences Edition), 2009, 36(1): 35-39 |
| |
| Authors: | GUO Hai-xu CHENG Cong-dian WU Ya-kun |
| |
| Affiliation: | 1.Computer Center;Liaonving University;Shenyang 110036;China;2.College of Mathematics and Systems Sciencel;Shenyang Normal University;Shenyang 110034;China |
| |
| Abstract: | Via constructing the auxiliary network,a new approximation algorithm is proposed and studied for the Maximum Concurrent Flow Problem 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 transformatio... |
| |
| Keywords: | bicriteria network multicommodity flow approximation scheme complexity approximation relation |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
