On the Complexity and Approximation of the Maximum Expected Value All-or-Nothing Subset

Noam Goldberg, Gabor Rudolf

An unconstrained nonlinear binary optimization problem of selecting a maximum expected value subset of items is considered. Each item is associated with a profit and probability. E…