0
$\begingroup$

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}|. $$

$\endgroup$
  • $\begingroup$ Welcome to MSE. It will be more likely that you will get an answer if you show us that you made an effort. $\endgroup$ – José Carlos Santos Jan 5 '18 at 16:24
  • $\begingroup$ @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? $\endgroup$ – alex_the_great Jan 12 '18 at 12:42
  • $\begingroup$ If the edges are sampled without replacement, the Chernoff bound does not apply here. Maybe you should confirm with your instructor. $\endgroup$ – PSPACEhard Jan 13 '18 at 4:22
  • $\begingroup$ @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? $\endgroup$ – alex_the_great Jan 13 '18 at 10:50
  • $\begingroup$ If you consider the max cut only, then the Chernoff bound suffices here. $\endgroup$ – PSPACEhard Jan 13 '18 at 12:14

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.