0
$\begingroup$

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

T3K14

$\endgroup$

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.