Untrusted Predictions Improve Trustable Query Policies
Untrusted Predictions Improve Trustable Query Policies
复制标题
不可信预测改进可信查询策略
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Jens Schloter
中科院分区：
文献类型：
--
作者：
T. Erlebach;Michael Hoffmann;M. S. D. Lima;Nicole Megow;Jens Schloter
我们研究如何利用（可能是机器学习）预测在模型中进行不确定性下的优化，允许算法查询未知数据。目标是最小化解决问题所需的查询数量。考虑到基本问题，如寻找元素的最小相交集或对它们进行排序，以及最小生成树问题，我们讨论了预测精度的不同度量，并设计了具有性能保证的算法，这些算法随着预测精度的提高而提高，并且相对于非常差的预测质量具有鲁棒性。我们还为最小生成树问题提供了新的结构见解，这可能在不考虑预测的可探索不确定性的背景下有用。我们的结果证明，在可探索不确定性模型中，不可信的预测可以绕过已知的下界。我们通过实验来补充我们的结果，这些实验经验证实了我们算法的性能。
We study how to utilize (possibly machine-learned) predictions in a model for optimization under uncertainty that allows an algorithm to query unknown data. The goal is to minimize the number of queries needed to solve the problem. Considering fundamental problems such as finding the minima of intersecting sets of elements or sorting them, as well as the minimum spanning tree problem, we discuss different measures for the prediction accuracy and design algorithms with performance guarantees that improve with the accuracy of predictions and that are robust with respect to very poor prediction quality. We also provide new structural insights for the minimum spanning tree problem that might be useful in the context of explorable uncertainty regardless of predictions. Our results prove that untrusted predictions can circumvent known lower bounds in the model of explorable uncertainty. We complement our results by experiments that empirically confirm the performance of our algorithms.
登录
查看更多内容
影响因子：
1.1
作者：
C. Durr;T. Erlebach;Nicole Megow;Julie Meißner
通讯作者：
C. Durr;T. Erlebach;Nicole Megow;Julie Meißner
DOI：
10.4230/lipics.esa.2021.7
发表时间：
2020-07
期刊：
--
影响因子：
--
作者：
Sepehr Assadi;Deeparnab Chakrabarty;S. Khanna
通讯作者：
Sepehr Assadi;Deeparnab Chakrabarty;S. Khanna
使用独立集查询进行近乎最优的边缘估计
DOI：
10.1137/1.9781611975994.177
发表时间：
2020
期刊：
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Chen, Xi;Levi, Amit;Waingarten, Erik
通讯作者：
Waingarten, Erik
查询的鲁棒背包问题
DOI：
10.1016/j.cor.2014.09.010
发表时间：
2015
期刊：
Comput. Oper. Res.
影响因子：
--
作者：
Goerigk;Schöbel
通讯作者：
Schöbel
可探索不确定性下的最小生成树的理论与实验
DOI：
10.1145/3422371
发表时间：
--
期刊：
Journal of Experimental Algorithmics (JEA)
影响因子：
--
作者：
J. Focke;N. Megow;J. Meißner
通讯作者：
J. Meißner