Query Minimization under Stochastic Uncertainty
Query Minimization under Stochastic Uncertainty
复制标题
DOI：
10.1016/j.tcs.2021.09.032
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
S. Chaplick;M. Halldórsson;M. S. D. Lima;Tigran Tonoyan
中科院分区：
文献类型：
--
作者：
S. Chaplick;M. Halldórsson;M. S. D. Lima;Tigran Tonoyan
我们研究了区间上具有随机不确定性信息的问题，这些信息的精确值可以通过付出代价来查询。我们的目标是设计一个自适应决策树，以找到问题的正确解决方案，同时最小化预期的总查询成本。我们证明，对于排序问题，这样的决策树可以在多项式时间内找到。对于寻找最小值数据项的问题，我们有一定的硬度证据。这与直觉相矛盾，因为最小问题在具有对抗性输入的在线设置和离线验证设置中都更容易。然而，可以利用随机假设来击败在线设置的确定性和随机近似下界。
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.