Problem statement:
Given an undirected graph $G = (V, E)$ with edge $e_i$ having two associated positive values $c_1, c_2$. Find a spanning tree $ST$ such that (ratio of the spanning tree): $$\frac{\sum{c_1}}{\sum{c_2}}$$ is minimum.
Motivation: competitive programming problem http://acm.timus.ru/problem.aspx?space=1&num=1447
This problem is solved as follows:
- Choose any ratio $x$.
- Assign weight $w(e) = c_1 - x \cdot c_2$ to each edge $e$.
- Find MST with any known algorithm (with respect to costs $w$).
- Assign ratio of this spanning tree to $x$. That is, $x \leftarrow ratio(MST)$.
- Output ratio if it hasn't changed compared to previous iteration; go to step 2 otherwise.
Could you please help me prove this solution by providing some hints? I don't understand why the ratio converges and what is the rate of convergence. Empirically, I know that convergence rate is logarithmic or faster as one can search ratio with binary search.
About the binary search solution. One should choose the first half of search range if sum of $w(e)$ in $ST$ is negative. The answer is found if this sum is zero. I also don't understand why this function is monotone.
I searched for some articles online but there aren't any free available.