# Estimate value of maximum cut in graph using Chernoff and union bounds

I read this: estimate value of maximum cut in graph by random sampling but I didn't understand how to solve my problem that is very similar.

My problem is let $G(V, E)$ be an unweighted and undirected graph. Let $S$ be a set of $\frac{24n}{ε^{2}}$ edges sampled uniformly at random without replacement. Assume that we only have access to the sampled edges of graph. Our goal is to estimate the weight of the max-cut $w(A, B) = |(A \times B) \cap E|$. Specifically, show that we can obtain a $(1 \pm \epsilon)$ approximate estimate by computing

$$|(A \times B) \cap S| \cdot \frac{|E|}{|S|},$$ while also showing that for any cut $(A', B')$ that is not the max-cut, the probability that the estimated cut value $|(A' \times B') \cap S| \cdot \frac{|E|}{|S|}$ is greater than

$$|(A' \times B') \cap E| + \epsilon \cdot |(A \times B) \cap E|$$

is small. Your algorithm has to succeed with probability at least $\frac{1}{2}$, but can take an arbitrary time.

Base your estimation on the following two probabilistic inequalities:

• Given a set of $|S|$ i.d.d. Bernoulli random variables $X_{1}, ..., X_{|S|}$ with expected value $\mu$, the Chernoff bounds state

$$P[\sum_{i=1}^{|S|}X_{i} > (1 + \epsilon)|S| \cdot \mu] < exp(- \frac{\epsilon^{2} \cdot |S| \cdot \mu}{3}) \text{ and}$$ $$P[\sum_{i=1}^{|S|}X_{i} < (1 - \epsilon)|S| \cdot \mu] < exp(- \frac{\epsilon^{2} \cdot |S| \cdot \mu}{2})$$

• The union bound states that given multiple not necessarily disjoint Bernoulli random variables $E_{i}$,

$$P[\cup E_{i}] \le \sum P[E_{i}|.$$

• Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. – José Carlos Santos Jan 5 '18 at 16:24
• @JoséCarlosSantos The issue is that I don't know how to start and solve the problem because I'm not really familiar with probability applied to randomized algorithm. Could you give me some explanation, please? – alex_the_great Jan 12 '18 at 12:42
• If the edges are sampled without replacement, the Chernoff bound does not apply here. Maybe you should confirm with your instructor. – PSPACEhard Jan 13 '18 at 4:22
• @PSPACE-Hard ok, I will verify, but in the case the edges are sampled with replacement and I have to prove the (1±ϵ) approximate estimate by computing $|(A \times B) \cap S| \cdot \frac{|E|}{|S|}$, do I have to use both Chernoff bounds and union bound or only the first? – alex_the_great Jan 13 '18 at 10:50
• If you consider the max cut only, then the Chernoff bound suffices here. – PSPACEhard Jan 13 '18 at 12:14