最大一致流问题的一个逼近算法

摘要：

通过建构辅助网络,以Korte和Vygen于2000年所给出的一个求最大多种物资网络流问题的逼近解的完全多项式算法作为子程序进行二分搜索, 给出了一个新的求解最大一致流问题的逼近算法. 然后,进行算法分析,说明了所建立的算法是拟多项式算法,并且给出与证明了一个有关输出的流与输入问题的解之间的逼近关系.该项工作表明从一个多种物资网络流问题的算法出发通过变换求解其他有关问题是可行的,并且为研究网络流问题提供了一种新的方法.

关键词：多物资网络流、逼近、算法、复杂性

所属期刊栏目：36

分类号：O157;O221(代数、数论、组合理论)

在线出版日期：2009-04-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：35-39