I struggle with the proof of Lemma 1 in the Paper "Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems" by Ravi and Sinha and hope this is the right community to ask for help.

Problem setting: There is a graph $G(V,E)$ with edge costs $c_e$ and a source vertex $s \in V$. Now there are $m$ scenarios for the second stage, with scenario $k$ specified by a destination vertex $t_k \in V$, a multiplicative cost scale factor $f_k$ and a probability $p_k$ with which the scenario occurs. If we chose a set of edges $E' \subset E$ in the first stage they have the cost $\sum_{e \in E'}c_e$. Then in the second stage a scenario $k$ occurs and we have to calculate a second stage solution for the shortest path $P_k$ between $s$ and $t_k$. We assume that the edges of the first stage ($E'$) have now cost zero while the remaining edge costs increase by $f_k$. This results in the following total first and second stage costs: $$\sum_{e \in E'}c_e + f_k \sum_{e \in P_k \setminus E'}c_e$$ The objective is to find the edge-subset $E'$ that minimizes the total costs.

Lemma: Now they say that there exists an optimum solution where the set $E'$ induces a tree containing the source $s$. I copy their proof here for simplicity:enter image description here

My problems and thoughts:

  • At first I had problems with the first sum $\sum_{P_k \ni e}p_kf_k \ge 1$, but now I think it means, that, in optimum, for any first stage edge the expected cost increase for all scenarios in which the edge is part of a shortest path must not be smaller than 1. Because if the sum was smaller than one, I would save cost if I get the edge in the second stage, which contradicts the optimum assumption. Is this correct?
  • Now i don't get, how this statement implies $\sum_{k \in K'} f_k \ge 1$. I get that for every scenario in $K'$ there is at least one edge used for $P_k$ for which the above statement is true, but I don't see the logical transition from the edges to the sum of cost factors. I see that this sum is already bigger than 1 if there is only one scenario with $f_k > 1$ but this doesn't help me to grasp the implification.

Thank you in advance



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.