Restricted inverse optimal value problem on linear programming under weighted $l_1$ norm

We study the restricted inverse optimal value problem on linear programming under weighted $l_1$ norm (RIOVLP ${}_1$). Given a linear programming problem $L{P}_c:\min \{cx\mathrm{\mid }Ax=b,x\ge 0\}$ with a feasible solution $x^0$ and a value $K$, we aim to adjust the vector $c$ to $\bar{c}$ such that $x^0$ becomes an optimal solution of the problem LP${}_{\bar{c}}$ whose objective value $\bar{c}{x}^0$ equals $K$. The objective is to minimize the distance $\mathrm{\parallel }\bar{c}-c{\mathrm{\parallel }}_1={\sum }_{j=1}^n{d}_j\mathrm{\mid }{\bar{c}}_j-c_j\mathrm{\mid }$ under weighted $l_1$ norm.Firstly, we formulate the problem (RIOVLP${}_1$) as a linear programming problem by dual theories. Secondly, we construct a sub-problem $(D^z)$, which has the same form as $L{P}_c$, of the dual (RIOVLP${}_1$) problem corresponding to a given value $z$. Thirdly, when the coefficient matrix $A$ is unimodular, we design a binary search algorithm to calculate the critical value $z^{\ast }$ corresponding to an optimal solution of the problem (RIOVLP${}_1$). Finally, we solve the (RIOV) problems on Hitchcock and shortest path problem, respectively, in $O(T_{MCF}\log \max \{d_{max},x_{max}^0,n\})$ time, where we solve a sub-problem $(D^z)$ by minimum cost flow in $T_{MCF}$ time in each iteration. The values $d_{max},x_{max}^0$ are the maximum values of $d$ and $x^0$, respectively.