1
$\begingroup$

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.

$\endgroup$

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.