-
题名有预算限制的最大并行流问题
- 1
-
-
作者
金鹤
赵大宇
-
机构
沈阳师范大学数学与系统科学学院
-
出处
《沈阳师范大学学报（自然科学版）》
CAS
2006年第4期399-402,共4页
-
基金
辽宁省高等学校科学研究基金资助项目(202112020)
-
文摘
改进了Garg N和K nemann给出的求解具有预算限制的最大并行流问题的近似算法,使得算法求出的目标函数值的近似性由原来的λ≥(1-ε)3OPT改进为λ≥1/(1+3ε)OPT,更接近最优值,而算法复杂性不变.给出数值例子,验证了算法改进的有效性.
-
关键词
有预算限制的最大并行流
近似算法
算法复杂性
-
Keywords
maximum concurrent flow with budget constraint
approximation algorithm
complexity of algorithm
-
分类号
O221.7
[理学—运筹学与控制论]
O157.5
[理学—基础数学]
-
-
题名有预算限制的最大多种物资流问题
- 2
-
-
作者
陈智博
唐恒永
-
机构
沈阳师范大学数学与系统科学学院
-
出处
《数学的实践与认识》
CSCD
北大核心
2006年第12期40-47,共8页
-
基金
国家自然科学基金(10471096)
-
文摘
研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O^(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性.
-
关键词
有预算限制的最大多种物资流
费用最小的最大多种物资流
全多项式时间近似算法
算法复杂性
-
Keywords
maximum multicommodity flow with budget constraint
minimum cost maximum multicommodity flow
fully polynomial time approximation scheme
complexity of algorithm
-
分类号
F252
[经济管理—国民经济]
F224
[经济管理—国民经济]
-
