Click here to flash read.
Given subsets of uncertain values, we study the problem of identifying the
subset of minimum total value (sum of the uncertain values) by querying as few
values as possible. This set selection problem falls into the field of
explorable uncertainty and is of intrinsic importance therein as it implies
strong adversarial lower bounds for a wide range of interesting combinatorial
problems such as knapsack and matchings. We consider a stochastic problem
variant and give algorithms that, in expectation, improve upon these
adversarial lower bounds. The key to our results is to prove a strong
structural connection to a seemingly unrelated covering problem with
uncertainty in the constraints via a linear programming formulation. We exploit
this connection to derive an algorithmic framework that can be used to solve
both problems under uncertainty, obtaining nearly tight bounds on the
competitive ratio. This is the first non-trivial stochastic result concerning
the sum of unknown values without further structure known for the set. With our
novel methods, we lay the foundations for solving more general problems in the
area of explorable uncertainty.
No creative common's license