| 有预算限制的最大多种物资流问题 |
| |
| 引用本文： | 陈智博,唐恒永.有预算限制的最大多种物资流问题[J].数学的实践与认识,2006,36(12):40-47. |
| |
| 作者姓名： | 陈智博 唐恒永 |
| |
| 作者单位： | 沈阳师范大学数学与系统科学学院,沈阳,110034 |
| |
| 摘 要： | 研究有预算限制的最大多种物资流问题,给出了这个问题的不依赖物资数k的全多项式时间近似算法,其算法复杂性是O~(-ε2m2).同时,利用有预算限制的最大多种物资流问题的研究结果,我们也得到了费用最小的最大多种物资流问题的近似算法和算法复杂性.
|
| 关 键 词： | 有预算限制的最大多种物资流 费用最小的最大多种物资流 全多项式时间近似算法 算法复杂性 |
| 修稿时间： | 2005年9月18日 |
Maximum Multicommodity Flow Problem with Budget Constraint |
| |
| CHEN Zhi-bo,TANG Heng-yong.Maximum Multicommodity Flow Problem with Budget Constraint[J].Mathematics in Practice and Theory,2006,36(12):40-47. |
| |
| Authors: | CHEN Zhi-bo TANG Heng-yong |
| |
| Abstract: | We discuss maximum multicommodity flow problem with budget constraint,present fully polynomial time approximation scheme for this problem that is independent of the number of commodities k,the complexity of the algorithm is (ε~(-2)m~2).Meanwhile,using the result of the maximum multicommodity flow problem with budget constraint,we also obtain the approximation scheme and the algorithm complexity for the minimum cost maximum multicommodity flow problem. |
| |
| Keywords: | maximum multicommodity flow with budget constraint minimum cost maximum multicommodity flow fully polynomial time approximation scheme complexity of algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
