Inverse problems of submodular functions on digraphs

CSpace

	Inverse problems of submodular functions on digraphs
	Cai, M ; Yang, X ; Li, Y
	2000-03-01
发表期刊	JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
ISSN	0022-3239
卷号	104 期号:3 页码:559-575
摘要	In this paper, we study the inverse problem of submodular functions on digraphs. Given a feasible solution x* for a linear program generated by a submodular function defined on digraphs, we try to modify the coefficient vector c of the objective function, optimally and within bounds, such that x* becomes an optimal solution of the linear program. It is shown that the problem can be formulated as a combinatorial linear program and can be transformed further into a minimum cost circulation problem. Hence, it can be solved in strongly polynomial time. We also give a necessary and sufficient condition for the feasibility of the problem. Finally, we extend the discussion to the version of the inverse problem with multiple feasible solutions.
关键词	inverse problems submodular functions digraphs minimum cost circulation strongly polynomial algorithms
语种	英语
WOS研究方向	Operations Research & Management Science ; Mathematics
WOS类目	Operations Research & Management Science ; Mathematics, Applied
WOS记录号	WOS:000087273700004
出版者	KLUWER ACADEMIC/PLENUM PUBL
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/15365
专题	中国科学院数学与系统科学研究院
通讯作者	Cai, M
作者单位	1.Chinese Acad Sci, Inst Syst Sci, Beijing, Peoples R China 2.Chinese Acad Sci, Lab Management Decis & Informat Syst, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Cai, M,Yang, X,Li, Y. Inverse problems of submodular functions on digraphs[J]. JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS,2000,104(3):559-575.
APA	Cai, M,Yang, X,&Li, Y.(2000).Inverse problems of submodular functions on digraphs.JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS,104(3),559-575.
MLA	Cai, M,et al."Inverse problems of submodular functions on digraphs".JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 104.3(2000):559-575.