网络流优化的快速数值逼近算法  

Fast numerical approximation algorithm for network flow optimization

作　　者：陈际平[1] 

机构地区：[1]陕西师范大学数学与信息科学学院,陕西西安710062

出　　处：《陕西师范大学学报（自然科学版）》2006年第1期18-20,共3页Journal of Shaanxi Normal University：Natural Science Edition

基　　金：国家自然科学基金资助项目(10571115)

摘　　要：研究了网络中最大共存流的优化问题,提出了网络流优化的快速数值逼近算法.该算法用被定性的共存流的轮流选取取代了传统的共存流随机选取,用O(k(ε-2+lgk)lgn)(其中k是共存流数,n是节点数,ε是精度要求)个单个流的最小成本流的计算来定性计算最大共存流的逼近解.其优点是在不增加总的运算时间的前提下,显著地改进了已知的定性上界,并且可以达到目前已知的随机上界.The optimization version of the maximum concurrent flow problem is considered, a new numerical algorithm is proposed, which can be computed determinitically in O（k （ε^-2 ＋ lg k ）lg n） （where k is the number of commodies, n is the number of nodes, and ε is the desired precision）. Using the deterministic round-robin selection to replace the random selection of commodities does not increase running time. Our bound significantly improves the currently known deterministic upper bounds and matches the best known randomized upper bound.

关 键 词：网络流优化 最大共存流 ε优化流 流的拥挤度 边容量 

分 类 号：O241.5[理学—计算数学] O221.7[理学—数学]