Consider a the splittable minimum cost flow problem on network $G(V,E,W,C)$ and a set of commodities $(s_i,t_i)$ with demand $d_i$ for $i=1,2,\dots,k$. Here, $w_e$ and $c_e$ is the weight of edge $e$ and the capacity of edge $e$, respectively. My question is what happens if we scale the demands and the capacities linearly but decrease the weights inversely. Consider the same problem on $G(V,E,W/\lambda, \lambda C)$ for the commodities $(s_i,t_i)$ with demand $\lambda d_i$ for $i=1,2,\dots,k$, where $\lambda$ is a constant. For each $\lambda$ we get a solution $OPT(\lambda)$. I am interested in the minimization of $OPT(\lambda)$ over $\lambda> 0$.

If someone can point me to the existing literature it will be helpful.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.