Minimum average weight cycle - Intuitive explanation

Question

In a directed graph, we look for a cycle with the lowest average weights. For example, a graph with nodes 1 and 2 with a path from 1 to 2 of length 2 and from 2 to 1 of length 4 will have a minimum average cycle of 3.

Do not look for a complex method (Karp), but a simple rollback with a trim solution. The explanation is given as "Solvable with return with important trim when the current average is greater than the best average life cycle cost found."

However, why does this method work? If we are halfway through the cycle, and the weight is more than the best average found, is it not possible that with small edges of the weight we can achieve a situation where our current cycle can drop lower than the best average found?

Edit: Here is an example of a problem: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2031

Answer 1

Assumes that the optimal solution for this graph is a cycle with maximum weight X.

There is some optimal cycle with edges e_1 , e_2 ... e_n , so avg(e_i) = X

For my proof, I accept all indices modulo n, so e_(n + 1) is e_1 .

Suppose our heuristic cannot find this solution, it means: for every i (no matter what we took first) there is j (we followed all the edges from i to j so far) that the average weight of the edge in the sequence e_i ... e_j larger than X (heuristic snapshot of this solution).

Then we can show that the average edge weight cannot be equal to X. Let's take the longest subsequence of contiguos, which is not trimmed by heuristics (having an average edge weight of at most X for each element). At least one e_i <= X , therefore, such a subsequence exists. For the first element e_k such a subsequence, there exists p such that avg(e_k ... e_p) > X First, take p . Now let's take k' = p + 1 and get another p' . We repeat this process until we hit our initial k again. The final p may not exceed the initial k , this means that the final subsequence contains the initial [e_k, e_p - 1] , which contradicts our construction for e_k . Now our sequence e_1 ... e_n completely covered by non-overlapping subsequences e_k ... e_p , e_k'...e_p' , etc., each of which has an average edge weight greater than X. Thus, we have a contradiction that avg(e_i) = X

Regarding your question:

If we are halfway through the cycle, and the weight is greater than the best is not found, what with small edges of the weight we can achieve a situation where our current cycle can fall below the average found?

Sure. But we can safely crop this solution, since later we will find the same cycle, starting from the other edge, which will not be shortened. My proof states that if we look at all the possible cycles on the chart, sooner or later we will find the optimal cycle.