2
$\begingroup$

In a series graph, each edge $e_i$ exists with probability $p_i$. And if you want to examine the existence of edge $e_i$, it will cost you $c_i$. I want to test the connectivity between source $s$ and destination $d$ with the minimum expexted cost.

I have figured out that the expected cost can be caculated below if the edge detection sequence is $e_1, e_2, \cdots e_n$:

$$E(cost) = c_1 + p_1 * (c_2 + p_2 * (c_3 + p_3 * (\cdots (c_{n-1} + p_{n-1} * c_n)\cdots))))$$

So is there a stretegy or algorithm to find out the minimum expected cost and the edge detection sequence?

enter image description here

$\endgroup$

1 Answer 1

2
$\begingroup$

Suppose that you test the edges in order. The expected cost is thus $$ \sum_{i=1}^n c_i \prod_{j=1}^{i-1} p_j. $$ Now suppose that we switch the order of $k$ and $k+1$. The two relevant terms are $$ c_k \prod_{j=1}^{k-1} p_j + c_{k+1} \prod_{j=1}^k p_j. $$ After switching $k$ and $k+1$, these two terms become $$ c_{k+1} \prod_{j=1}^{k-1} p_j + c_k p_{k+1} \prod_{j=1}^{k-1} p_j. $$ Dividing by $\prod_{j=1}^{k-1} p_j$, these two expressions become $$ c_k + p_k c_{k+1} \\ c_{k+1} + p_{k+1} c_k $$ The switch leads to an improvement if $$ c_k + p_k c_{k+1} > c_{k+1} + p_{k+1} c_k \\ \Longleftrightarrow \\ c_k (1-p_{k+1}) > (1-p_k) c_{k+1} \\ \Longleftrightarrow \\ \frac{c_k}{1-p_k} > \frac{c_{k+1}}{1-p_{k+1}}. $$ This suggests testing the edges in increasing order of $$ \frac{c_i}{1-p_i}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.