辽宁大学学报（自然科学版）
遼寧大學學報（自然科學版）
료녕대학학보（자연과학판）
JOURNAL OF LIAONING UNIVERSITY(NATURAL SCIENCE EDITION)
2009年
1期
35-39
,共5页
多物资网络流%逼近%算法%复杂性
多物資網絡流%逼近%算法%複雜性
다물자망락류%핍근%산법%복잡성
通过建构辅助网络,以Korte和Vygen于2000年所给出的一个求最大多种物资网络流问题的逼近解的完全多项式算法作为子程序进行二分搜索, 给出了一个新的求解最大一致流问题的逼近算法. 然后,进行算法分析,说明了所建立的算法是拟多项式算法,并且给出与证明了一个有关输出的流与输入问题的解之间的逼近关系.该项工作表明从一个多种物资网络流问题的算法出发通过变换求解其他有关问题是可行的,并且为研究网络流问题提供了一种新的方法.
通過建構輔助網絡,以Korte和Vygen于2000年所給齣的一箇求最大多種物資網絡流問題的逼近解的完全多項式算法作為子程序進行二分搜索, 給齣瞭一箇新的求解最大一緻流問題的逼近算法. 然後,進行算法分析,說明瞭所建立的算法是擬多項式算法,併且給齣與證明瞭一箇有關輸齣的流與輸入問題的解之間的逼近關繫.該項工作錶明從一箇多種物資網絡流問題的算法齣髮通過變換求解其他有關問題是可行的,併且為研究網絡流問題提供瞭一種新的方法.
통과건구보조망락,이Korte화Vygen우2000년소급출적일개구최대다충물자망락류문제적핍근해적완전다항식산법작위자정서진행이분수색, 급출료일개신적구해최대일치류문제적핍근산법. 연후,진행산법분석,설명료소건립적산법시의다항식산법,병차급출여증명료일개유관수출적류여수입문제적해지간적핍근관계.해항공작표명종일개다충물자망락류문제적산법출발통과변환구해기타유관문제시가행적,병차위연구망락류문제제공료일충신적방법.
