The minimum expectation selection problem

DOI10.1002/RSA.10061MaRDI QIDQ4798168zbMATH OpenOpenAlexFDO

Authors David Eppstein, George S. Lueker

Publication date 19 March 2003

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0110011

zbMATH Keywords

approximation algorithmcomplexitydiscrete probability distributionselection problem

Mathematics Subject Classification ID

Combinatorial probability (60C05)

Abstract: We define the min-min expectation selection problem (resp. max-min expectation selection problem) to be that of selecting k out of n given discrete probability distributions, to minimize (resp. maximize) the expectation of the minimum value resulting when independent random variables are drawn from the selected distributions. We assume each distribution has finitely many atoms. Let d be the number of distinct values in the support of the distributions. We show that if d is a constant greater than 2, the min-min expectation problem is NP-complete but admits a fully polynomial time approximation scheme. For d an arbitrary integer, it is NP-hard to approximate the min-min expectation problem with any constant approximation factor. The max-min expectation problem is polynomially solvable for constant d; we leave open its complexity for variable d. We also show similar results for binary selection problems in which we must choose one distribution from each of n pairs of distributions.

Review text

Suppose that the distributions of \(n\) independent random variables \(Y_i\), \(i\in [n]\), are given, and each of the random variables is limited to \(d\) different values. For given \(k\), the min-min expectation subset selection problem is defined to be the problem of choosing a subset \(S\in [n]\) with \(|S|=k\) for which \({\mathbf E}(\min_{i\in S} Y_i)\) is minimized. Analogously, in the max-min expectation subset selection problem the value should be maximized through the same process. Two more closely related problems are defined -- min-min expectation binary selection problem and max-min expectation binary selection problem. For \(2n\) given independent random variables \(Y_{i,s}\), \(i\in [n]\), \(s\in\{0,1\}\), the function \(\xi:[n] \rightarrow \{0,1\}\) should be found to minimize (resp. maximize) \({\mathbf E}(\min_{i\in [n]} Y_{i,\xi(i)})\). It is proven that if \(d>2\) is fixed, then the min-min expectation subset selection problem is \(\mathcal{NP}\)-hard and it admits a fully polynomial approximation scheme. If \(d\) is an arbitrary integer, it is \(\mathcal{NP}\)-hard to approximate it within any constant approximation factor. On the other hand, it is proven that the max-min expectation problem is in \(\mathcal{P}\) for constant \(d\), whereas its complexity for \(d\) being a variable is open. The corresponding problems on complexity and approximability for binary selection problems are also addressed and they turn out to be (respectively) similar as in the first case.

Recommendations

• On the complexity and approximation of the maximum expected value all-or-nothing subset
• Approximating the min-max (regret) selecting items problem
• Robust recoverable and two-stage selection problems
• A randomized algorithm for the min-Max selecting items problem with uncertain weights
• scientific article; zbMATH DE number 3866373

Cited in

(1)

• On the complexity and approximation of the maximum expected value all-or-nothing subset

This page was built for publication: The minimum expectation selection problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4798168)