Min-Min Expectation Selection Problem

Title: Min-Min Expectation Selection Problem

Abstract: The min-min expectation selection problem is a problem that involves selecting k out of n given discrete probability distributions to minimize the expected value of the minimum value resulting when independent random variables are drawn from the selected distributions. The max-min expectation problem is about maximizing this value. This problem is important in various fields, such as peer-to-peer file sharing and editing where the goal is to select the best options to minimize expected time or maximize expected quality.

The researchers found that if dis is a constant greater than 2, the min-min expectation problem is NP-complete but admits a fully polynomial time approximation scheme. For any integer d, 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, and the researchers left open its complexity for variable d. They also showed similar results for binary selection problems, where they need to choose one distribution from each pair of distributions.

Implications: This research has significant implications for various fields that deal with selection problems involving discrete probability distributions. It provides a better understanding of the complexity of these problems and helps in developing more efficient algorithms and approaches for solving them. It also has practical applications in real-world scenarios, such as file sharing, editing, and other decision-making processes where the goal is to minimize expected time or maximize expected quality.

Link to Article: https://arxiv.org/abs/0110011v1 Authors: arXiv ID: 0110011v1