CSpace
 Inverse problems of submodular functions on digraphs Cai, M; Yang, X; Li, Y 2000-03-01 Source Publication JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS ISSN 0022-3239 Volume 104Issue:3Pages:559-575 Abstract 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. Keyword inverse problems submodular functions digraphs minimum cost circulation strongly polynomial algorithms Language 英语 WOS Research Area Operations Research & Management Science ; Mathematics WOS Subject Operations Research & Management Science ; Mathematics, Applied WOS ID WOS:000087273700004 Publisher KLUWER ACADEMIC/PLENUM PUBL Citation statistics Document Type 期刊论文 Identifier http://ir.amss.ac.cn/handle/2S8OKBNM/15365 Collection 中国科学院数学与系统科学研究院 Corresponding Author Cai, M Affiliation 1.Chinese Acad Sci, Inst Syst Sci, Beijing, Peoples R China2.Chinese Acad Sci, Lab Management Decis & Informat Syst, Beijing, Peoples R China Recommended CitationGB/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.
 Files in This Item: There are no files associated with this item.
 Related Services Recommend this item Bookmark Usage statistics Export to Endnote Google Scholar Similar articles in Google Scholar [Cai, M]'s Articles [Yang, X]'s Articles [Li, Y]'s Articles Baidu academic Similar articles in Baidu academic [Cai, M]'s Articles [Yang, X]'s Articles [Li, Y]'s Articles Bing Scholar Similar articles in Bing Scholar [Cai, M]'s Articles [Yang, X]'s Articles [Li, Y]'s Articles Terms of Use No data! Social Bookmark/Share