---
# System prepended metadata

title: Alon et al. analysis for MW

---

# Alon et al. analysis for MW

There exist a bisection $(S,T)$ which scores $0.5 OPT$.
Let $C$ be the weight of the cut.
After that, we do random partitioning, which scores $1/3 \cdot 1/2 \cdot (1 - C) = \frac 16 (1 - C)$.

Overall we get $C/2 +(1 - C)/6 = 1/6 + C/3$

Hence we just assume $C = 1/2$.

In this case we get at least $\alpha B(G) + 1/3 * 1/2 * 1/2 \ge 0.878 * 1/2 + 1/12$

# Proposed algorithm

1. Balanced Max-2-SAT => (S,T) => two random paths like in our paper

Let's say that we maximize $w(S) + w(S,T)$ then we score:
$$5/6 w(S) + 3/4 w(S,T) + 1/3 w(T) = 1/3 W + (1/2 w(S) + 5/12 w(S,T))$$

3. TBD

Concern with 1 is that it doesn't give good approx on either complete or complete bipartite.

Let $D_1 = w(S)$ and $D_2 = w(S,T)$.
Path solution gives us $1/3 + 1/2 D_1 + 5/12 D_2$.

Bisection solution gives us $w(S,T) + 1/3 (1 - w(S,T)) = 1/3 + 2/3 D_2$.

When selecting the best of them, we have at least $1/3 + 4/9 (D_1 + D_2)$.

For the complete bipartite graph, $OPT = W$, but MAX2SAT gives us $W (1/3 + 0.94 * 4/9) = W \cdot 0.751$.

For the complete graph, $OPT = 2/3 W$, but MAX2SAT gives us $W (1/3 + 0.94 * 4/9 * 3/4) = W \cdot 0.64$

We get $1/3 + 4/9 \cdot (w(S) + w(S,T)) \ge 1/3 + 4/9 \cdot 0.94 \cdot (w(S^*) + w(S^*,T^*))$.