论文标题
在随机不确定性下查询最小化
Query Minimization under Stochastic Uncertainty
论文作者
论文摘要
我们研究了随机不确定性信息的问题，可以通过支付成本来查询确切价值的间隔。目的是设计一个自适应决策树，以找到对问题的正确解决方案，同时最大程度地减少预期的总查询成本。我们表明，对于分类问题，可以在多项式时间内找到这样的决策树。对于以最低价值查找数据项的问题，我们有一些硬度证据。这与直觉相矛盾，因为在在线设置的对抗性输入和离线验证设置中，最小问题都更容易。但是，可以利用随机假设来击败在线设置的确定性和随机近似下限。
We study problems with stochastic uncertainty information on intervals for which the precise value can be queried by paying a cost. The goal is to devise an adaptive decision tree to find a correct solution to the problem in consideration while minimizing the expected total query cost. We show that, for the sorting problem, such a decision tree can be found in polynomial time. For the problem of finding the data item with minimum value, we have some evidence for hardness. This contradicts intuition, since the minimum problem is easier both in the online setting with adversarial inputs and in the offline verification setting. However, the stochastic assumption can be leveraged to beat both deterministic and randomized approximation lower bounds for the online setting.
