2
$\begingroup$

A polynomial random process satisfying the following properties converts a fractional point $(x_1, x_2, \ldots, x_n) \in \mathcal{P}$, $(x_i \in [0,1])$ to a random integer point $(X_1, X_2, \ldots, X_n) \in \mathbb{Z}(\mathcal{P})$, $(X_i \in \{0,1\})$:

  • $\mathbb{E}[X_i]=x_i$, for all $i \in [n]$.
  • For any $S \subseteq [n]$, $\mathbb{E}[\prod_{i\in S} X_i] \leq \prod_{i \in S} x_i$ and $\mathbb{E}[\prod_{i\in S} (1-X_i)] \leq \prod_{i \in S} (1-x_i)$ (negative correlation).

An example is the dependent randomized rounding by Chekuri, Vondrak, and Zenklusen (http://arxiv.org/pdf/0909.4348v2.pdf).

We focus on the dependent randomized rounding. Given a point $x \in \mathcal{P}$, where $\mathcal{P}$ is a matroid polytope, let us assume that $X$ is the outcome of the random process (the dependent randomized rounding). Can we evaluate the value of $Pr\Big(\displaystyle \bigwedge_{i \in S} X_i=1 \Big)$ for some $S \subseteq [n]$? Shall we use sampling for this purpose?

That would be great if you can comment on this.

Improve this question
$\endgroup$
8
  • $\begingroup$ Are you assuming each $X_i\in [0,1]$? Otherwise the conditions on the products seem strange... $\endgroup$ – Neal Young Mar 28 '15 at 15:33
  • $\begingroup$ @NealYoung, Yes, I assume $x_i \in [0,1]$ and $X_i \in \{0,1\}$. $\endgroup$ – salmAn Mar 28 '15 at 18:49
  • $\begingroup$ What exactly are you interested in bounding with a Chernoff-like bound? E.g. are you interested in bounding $\Pr[\sum_i X_i \ge (1+\epsilon)\sum_i x_i]$? $\endgroup$ – Neal Young Mar 29 '15 at 13:40
  • $\begingroup$ What about thm's 3.2 and 3.4 of epubs.siam.org/doi/pdf/10.1137/S0097539793250767 ? $\endgroup$ – Neal Young Mar 29 '15 at 13:50
  • $\begingroup$ @NealYoung thank you very much for your comments. What I'm interested in is basically $Pr\Big(\displaystyle \bigwedge_{i \in S} X_i=1 \Big)$. I updated the question to make it clearer. $\endgroup$ – salmAn Mar 29 '15 at 18:50
1
$\begingroup$

I think that in principle it would take exponential time to compute this probability exactly. Hence sampling would be the only option here, although you would have to settle for additive and multiplicative approximation here. Can I ask you about the problem in which you need this value to be computed?

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.