Inverse polymatroidal flow problem
文献类型：期刊论文
| 作者 | Cai, MC; Yang, XG; Li, YJ |
| 刊名 | JOURNAL OF COMBINATORIAL OPTIMIZATION
 |
| 出版日期 | 1999-07-01 |
| 卷号 | 3期号:1页码:115-126 |
| ISSN号 | 1382-6905 |
| 关键词 | inverse problem polymatroidal flow minimum cost circulation combinatorial strongly polynomial algorithm |
| 英文摘要 | Let D = (V, A) be a directed graph, for each vertex v is an element of V, let Delta(+)(upsilon) and Delta(-)(upsilon) denote the sets of arcs leaving and entering upsilon, F-upsilon(+) and F-upsilon(-) be intersecting families on Delta(+)(upsilon) and Delta(-)(upsilon), respectively, and rho(upsilon)(+) : F-upsilon(+) --> R+ and rho(upsilon)(-) : F-upsilon(+) --> R+ be submodular functions on intersecting pairs. A flow f : A --> R is feasible if f(Delta(+)(upsilon)) = f(Delta-(upsilon)) For All upsilon is an element of V, f(S) less than or equal to rho(upsilon)(+)(S) For All S is an element of F-upsilon(+), upsilon is an element of V, f(S) less than or equal to rho(upsilon)(-)(S) For All S is an element of F-upsilon(-), upsilon is an element of V, f(e) greater than or equal to 0 For All e is an element of A, Given a cost function c on A, the minimum cost polymatroidal flow problem is to find a feasible flow f with minimum cost Sigma{c(e)f(e) \ e is an element of A}, it is a significant generalization of many combinatorial optimization problems. Given a feasible flow f*, cost and restriction functions on A, the inverse polymatroidal flow problem is to modify c, optimally and with bounds, such that f* becomes a minimum cost polymatroidal flow under the modified cost. It is shown in this paper that the inverse problem can be formulated as a combinatorial linear program and can be further transformed into a minimum cost circulation problem. Hence it can be solved efficiently by strongly polynomial combinatorial algorithms. We also give a necessary and sufficient condition for the feasibility of the inverse problem. |
| WOS研究方向 | Computer Science ; Mathematics |
| 语种 | 英语 |
| 出版者 | KLUWER ACADEMIC PUBL |
| WOS记录号 | WOS:000081774600009 |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/14894]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Cai, MC |
| 作者单位 | Acad Sinica, Inst Syst Sci, MADIS, Beijing 100080, Peoples R China |
| 推荐引用方式 GB/T 7714 | Cai, MC,Yang, XG,Li, YJ. Inverse polymatroidal flow problem[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,1999,3(1):115-126. |
| APA | Cai, MC,Yang, XG,&Li, YJ.(1999).Inverse polymatroidal flow problem.JOURNAL OF COMBINATORIAL OPTIMIZATION,3(1),115-126. |
| MLA | Cai, MC,et al."Inverse polymatroidal flow problem".JOURNAL OF COMBINATORIAL OPTIMIZATION 3.1(1999):115-126. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。