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. Further, we handle for the first time uncertainty in the constraints in a value-query model. With our novel methods, we lay the foundations for solving more general problems in the area of explorable uncertainty.
翻译:考虑到不确定值子集,我们通过尽可能少的数值来研究确定最低总价值子集(不确定值之和)的问题。这个设定的选定问题属于可探索不确定性的领域,具有内在重要性,因为它意味着对诸如Knapsack和匹配等一系列有趣的组合问题具有强烈的对立性下限。我们考虑一个随机问题变体,并给出算法,期望这些对立的下限会有所改进。我们结果的关键是证明一个似乎无关的结构性联系,通过线性编程公式来填补受限的不确定性问题。我们利用这一联系来得出一个算法框架,可用来解决在不确定情况下的两种问题,在竞争比率上获得近乎紧凑的界限。这是第一个关于未知价值之和而没有已知的更进一步结构的非边际的随机结果。此外,我们第一次处理价值-质模型中制约的不确定性。我们采用新的方法,为在可探索不确定性领域解决更一般性的问题打下了基础。