摘要：研究了KarakostasG给出的求解最大并行流问题的一个近似算法，将其算法的参数进行了改进，给出了算法的时间复杂性不依赖于物资数k的广义最大并行流的全多项式时间近似算法，该算法只适用于广义的lossy网络。用改进后算法求出的目标函数值更接近于最优值，对该近似算法的近似性和算法的时间复杂性进行了证明。最后，用C语言编程，计算数值例子，通过对比充分验证了改进后算法的正确性和有效性。

关键词：广义最大并行流 全多项式时间近似算法 算法复杂性 lossy网络 获得因子 

单位：沈阳师范大学; 沈阳110034