Inverse Problems of Submodular Functions on Digraphs

M. Cai, X. Yang and Y. Li
Additional contact information
M. Cai: Chinese Academy of Sciences
X. Yang: Chinese Academy of Sciences
Y. Li: Chinese Academy of Sciences

Journal of Optimization Theory and Applications, 2000, vol. 104, issue 3, No 4, 559-575

Abstract: 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.

Keywords: inverse problems; submodular functions; digraphs; minimum cost circulation; strongly polynomial algorithms (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1023/A:1004685508517 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:104:y:2000:i:3:d:10.1023_a:1004685508517

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1004685508517

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().