1
$\begingroup$

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?

$\endgroup$

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.