I have an unweighted and undirected graph G(V, E) and a set S of $\frac{24n}{\epsilon^2}$ edges sampled uniformly at random without replacement. Now the problem is that I have to obtain a $(1 \pm \epsilon)$ approximate estimate by computing $|(A \times B) \cap S| \cdot \frac{|E|}{|S|}$ where the optimal weight of the max-cut is $|(A \times B) \cap E|$ and considering the Chernoff bounds: $$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})$$

and the union bound that states: given multiple not necessarily disjoint Bernoulli random variables $E_{i}$,

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

I defined for $1 \le i \le |S|$ Bernoulli random variables:

$$ X_{i} = \begin{cases} 1 \quad \text{ if the i-th edge in S belongs to the max-cut (A, B)} \\ 0 \quad \text{ otherwise} \end{cases} $$ and then I compute the expected value:

$E[X_{i}] = \mu = P[X_{i} = 1] = \frac{|(A \times B) \cap E|}{|E|}$

where $X_{1} + X_{2} + ... + X_{|S|} = |(A \times B) \cap S|$

But now how can I obtain the approximate estimate considering the Chernoff and union bounds above?


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.