---
# System prepended metadata

title: '(0.29, 0.29, 0.42) case'

---

# (0.29, 0.29, 0.42) case


Suppose $a = b = 0.29$ and $c = 0.42$. 
When we are splitting $A$ let $p_{AB} = 0.21/0.29 \approx 0.724$ and $p_{AC} = 0.08/0.29 \approx 0.276$:
$$(p_{AB}^2 + p_{AC}^2) w(A) + w(B) + w(C) + p_{AB} w(A,B) + p_{AC} w(A,C)$$
Which is approximately:
$$0.6 w(A) + w(B) + w(C) + 0.724 w(A,B) + 0.276 w(A,C)$$


Similarly when splitting $B$ for $p_{BA} = 0.21/0.29 \approx 0.724$ and $p_{BC} = 0.08/0.29 \approx 0.276$ we have:
$$(p_{BA}^2 + p_{BC}^2) w(B) + w(A) + w(C) + p_{BA} w(A,B) + p_{BC} w(B,C)$$
Which is approximately:
$$0.6 w(B) + w(A) + w(C) + 0.724 w(A,B) + 0.276 w(B,C)$$

Finally, when splitting $C$ for $p_{CA} = 1/2$ and $p_{CB} = 1/2$ we have:
$$0.5 w(C) + w(A) + w(B) + 0.5 w(B,C) + 0.5 w(A, C)$$

Let's set $p_a = p_b = 0.35$ and $p_c = 0.3$ for the probabilities of splitting $A, B$ and $C$ respectively. Thus when we combine the three expressions above we get:
$$(0.6 * 0.35 + 0.35 + 0.3) w(A) \\+ (0.6 * 0.35 + 0.35 + 0.3) w(B) \\+ (0.5 * 0.3 + 0.35 + 0.35) w(C) \\ + (0.724 * 0.35 + 0.724 * 0.35) * w(A,B)  \\ + (0.276 * 0.35 + 0.5 * 0.3) * w(A,C) \\ +  (0.276 * 0.35 + 0.5 * 0.3) * w(B,C)$$

Calculating the numbers we get:
$$0.86 * w(A) + 0.86 * w(B) + 0.85 * w(C) + 0.5 * w(A,B) + 0.247 * w(A,C) + 0.247 * w(B,C)$$

Recall that the upper bound is:
$$OPT \le w(A) + w(B) + w(C) + 0.42 (w(A,B) + w(B,C) + w(A,C))$$

Let $w(A) + w(B) + w(C) = \alpha$ and $w(A,B) + w(B,C) + w(A,C) = \beta$.
Then the first part of our algorithm can score at least:
$$GW * 2/3 * (0.86 \alpha + 0.247 \beta),$$
while random scores at least $1/3 (\alpha + \beta)$ and $OPT \le \alpha + 0.42 \beta$. We will show that approximation $\gamma$ is at least $0.45$.

Suppose $\alpha = t\beta$ for $t \le 1$. Then random scores at least $\frac13 \beta (1 + t)$ while $0.45 OPT \le 0.45(t + 0.42) \beta$.
So we need to show that $\frac{1 + t}{3} \ge 0.45 t + 0.189$ which holds for all $t \in [0,1]$.
Otherwise, $\alpha = t \beta$ for $t > 1$. In this case our solution scores at least:
$$GW * 2/3 * (0.86 \alpha + 0.247 \beta) = \beta * 0.87 * (2/3) (0.86 t + 0.247) \ge (0.45 t + 0.189) \beta,$$
where the last inequality holds for all $t > 1$ since $0.87 * 2/3 * 0.86 \approx 0.5$ and $0.87 * (2/3) * 0.247 \approx 0.143$.



<!--
Suppose $1/3(\alpha + \beta) \ge 0.45 (\alpha + 0.42 \beta) = 0.45 \alpha + 0.189 \beta$. Then we are done (and otherwise we have $0.117 \alpha > 0.144 \beta$ or $\alpha > 1.23 \beta$).
Otherwise, we need to show that $0.87 * 2/3 * (0.86 \alpha + 0.247 \beta) \ge 0.45 (\alpha + 0.42 \beta)$.
This simplifies to:
$$0.5 \alpha + 0.143 \beta \ge 0.45 \alpha + 0.189 \beta$$
$$0.05\alpha \ge 0.046 \beta$$
-->
