I am working on the following exercise:
Consider an undirected graph $G(V,E)$ with two real edge weights $w_e$ and $v_e$. Assume that $\sum_{e \in E_{T^*}} v_e >0$.
Find a spanning tree $T^* = (V,E_{T^*})$ that minimises
$$\frac{\sum_{e \in E_{T^*}} w_e}{\sum_{e \in E_{T^*}} v_e}$$
in polynomial time.
I suppose we have to define a new weight function that combines $w_e$ with $v_e$ and to use the algorithms we already have for minimum spanning trees. But I do not see how I could do that. Could you help me?
Use bounds on the numerator and denominator to obtain bounds for the ratio. Then apply bisection search on the resulting interval $[L,U]$ for the ratio. To test whether there is a tree with ratio at most $r$, solve a minimum spanning tree problem with weights $w_e-r v_e$ and compare to 0. There will be $O(\log_2 (U-L))$ MST calls.