CSpace
Inverse problems of submodular functions on digraphs
Cai, M; Yang, X; Li, Y
2000-03-01
Source PublicationJOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS
ISSN0022-3239
Volume104Issue:3Pages:559-575
AbstractIn 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.
Keywordinverse problems submodular functions digraphs minimum cost circulation strongly polynomial algorithms
Language英语
WOS Research AreaOperations Research & Management Science ; Mathematics
WOS SubjectOperations Research & Management Science ; Mathematics, Applied
WOS IDWOS:000087273700004
PublisherKLUWER ACADEMIC/PLENUM PUBL
Citation statistics
Cited Times:3[WOS]   [WOS Record]     [Related Records in WOS]
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/15365
Collection中国科学院数学与系统科学研究院
Affiliation1.Chinese Acad Sci, Inst Syst Sci, Beijing, Peoples R China
2.Chinese Acad Sci, Lab Management Decis & Informat Syst, Beijing, Peoples R China
Recommended Citation
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.
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
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.