论文标题
通过覆盖技术在可探索的随机不确定性下进行选择
Set Selection under Explorable Stochastic Uncertainty via Covering Techniques
论文作者
论文摘要
给定不确定值的子集，我们通过查询尽可能少的值来识别最小总价值（不确定值的总和）的子集的问题。此设定的选择问题属于可探索的不确定性领域，并且在其中具有内在的重要性，因为它暗示着强大的对抗性下限，对于多种有趣的组合问题，例如knapsack和napSack和匹配。我们考虑一个随机问题变体，并给出算法，以期预期这些对抗性下限。我们结果的关键是证明通过线性编程公式与约束的看似无关的涵盖问题有着强烈的结构联系。我们利用这种联系来得出一个算法框架，该算法可用于在不确定性下解决这两个问题，从而获得竞争比率几乎紧密的界限。这是关于未知值的总和而没有集合已知的未知值之和的第一个非平凡随机结果。借助我们的新方法，我们为解决可探索的不确定性领域中更一般的问题奠定了基础。
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.
