有预算限制的最大并行流问题

Maximum Concurrent Flow Problem with Budget Constraint

改进了Garg N和K nemann给出的求解具有预算限制的最大并行流问题的近似算法,使得算法求出的目标函数值的近似性由原来的λ≥(1-ε)3OPT改进为λ≥1/(1+3ε)OPT,更接近最优值,而算法复杂性不变.给出数值例子,验证了算法改进的有效性.

We improve the approximation algorithm for maximum concurrent flow with budget constraint given by Garg N and Koenemann withno changing in complexity of the algorithm, which makes the objective function value change from λ≥（ 1 -ε ）^3 OPT to λ/（ 1 ＋ 3ε） OPT. The new objective function value is closer to the optimal value. By computing a numerical example, we verify the effectiveness of the improvement.