Publisher： Springer Publishing Company
ISSN： 0022-3239
Source： Journal of Optimization Theory and Applications, Vol.104, Iss.3, 2000-03, pp. : 559-575
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
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.
Related content
Minimizing symmetric submodular functions
By Queyranne M.
Mathematical Programming, Vol. 82, Iss. 1, 1998-06 ,pp. :
Access to resources
Recommend
Inverse Bessel Functions: Solution for the Zeros
STUDIES IN APPLIED MATHEMATICS, Vol. 97-1421, Iss. 1, 1957-04 ,pp. :
Inverse Bessel Functions: Solution for the Zeros
STUDIES IN APPLIED MATHEMATICS, Vol. 36, Iss. 1, 1957-04 ,pp. :