Assume you have $n$ independent binary variables $\{x\_1,\dots,x\_n\}$ and for each variable $x\_i$ you know that its value is equal to $1$ with a probability $p\_i$. I would like to enumerate the joint assignments of these variables in such a way that in $k$ steps I capture as much volume of the joint probability mass function as possible. Does there exist some approximation algorithm which runs faster than the algorithm which enumerates the assignments according to their joint probability $\Pi p\_i$. Or something related?



Choosing $k$ different assignments of binary variables in order to capture the largest volume of the joint probability distribution
You want to find a $k$-subset $S\subseteq\{0,1\}^n$ to maximize
$$\sum\_{(y\_1,\dots,y\_n)\in S} \prod\_{i=1}^n \left(p\_{i}y\_i+(1-p\_i)(1-y\_i)\right).$$


Equivalently, find the $k$ largest (with multiplicity)
$$\prod\_{i=1}^n \left(p\_{i}y\_i+(1-p\_i)(1-y\_i)\right).$$


Equivalently, find the $k$ largest (with multiplicity)
$$\sum\_{i=1}^n \left((\log p\_{i})y\_i+(\log(1-p\_i))(1-y\_i)\right).$$


Some integer linear programming (ILP) solvers have an option to find the $k$ best solutions. An alternative approach to get the $k$ best solutions is to call an ILP solver $k$ times. After each solve, yielding optimal solution $\hat{y}\in\{0,1\}^n$, impose an additional no-good cut
$$\sum\_{i:\hat{y}\_i = 0} y\_i + \sum\_{i:\hat{y}\_i = 1} (1 - y\_i) \ge 1$$
that excludes only that solution.


