0
$\begingroup$

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:

  1. Choose any ratio $x$.
  2. Assign weight $w(e) = c_1 - x \cdot c_2$ to each edge $e$.
  3. Find MST with any known algorithm (with respect to costs $w$).
  4. Assign ratio of this spanning tree to $x$. That is, $x \leftarrow ratio(MST)$.
  5. 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.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ It looks like the algorithm was described in a confusing way. I will write an answer. By the way, can you edit the question to add the condition that $c_1(e_i), c_2(e_i)$ are positive for all $i$? (Or that the sum of $c_2$ of edges of any spanning tree is greater than 0, which is, however, a condition that is not much more enlightening.) however.) $\endgroup$ – John L. Apr 27 '19 at 16:36
  • $\begingroup$ The rate of convergence is elusive. I cannot prove it is no slower than logarithmic yet. $\endgroup$ – John L. May 4 '19 at 18:52

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.