Inverse polymatroidal flow problem

CSpace

	Inverse polymatroidal flow problem
	Cai, MC; Yang, XG; Li, YJ
	1999-07-01
发表期刊	JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN	1382-6905
卷号	3 期号:1 页码:115-126
摘要	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.
关键词	inverse problem polymatroidal flow minimum cost circulation combinatorial strongly polynomial algorithm
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS记录号	WOS:000081774600009
出版者	KLUWER ACADEMIC PUBL
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/14895
专题	中国科学院数学与系统科学研究院
通讯作者	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.