Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing
Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing
复制标题
DOI：
10.4230/lipics.esa.2021.59
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Thomas Lavastida;Benjamin Moseley;R. Ravi;Chenyang Xu
中科院分区：
文献类型：
--
作者：
Thomas Lavastida;Benjamin Moseley;R. Ravi;Chenyang Xu
本文提出了一种新的模型，用于通过对算法性能的最坏情况界限之外的有用预测来增强算法。通过改进现有模型，我们的模型确保预测在形式上是可学习的且对实例具有鲁棒性。可学习性保证了可以从过去的数据中有效地构建预测。实例鲁棒性在形式上确保了预测对问题输入的适度变化具有鲁棒性。此外，鲁棒性模型确保可以客观地比较两个不同的预测，解决了先前模型中的一个缺陷。本文确立了满足这些性质的预测的存在性。本文考虑了具有预测的在线算法，用于网络流分配问题和受限分配完工时间最小化问题。对于这两个问题，确立了三个关键性质：存在能给出接近最优解的有用预测，这些预测对误差的鲁棒性，即随着基础问题实例的变化误差平滑地降低，并且我们证明了可以从少量先前实例样本中学习到高质量的预测。
This paper proposes a new model for augmenting algorithms with useful predictions that go beyond worst-case bounds on the algorithm performance. By refining existing models, our model ensures predictions are formally learnable and instance robust. Learnability guarantees that predictions can be efficiently constructed from past data. Instance robustness formally ensures a prediction is robust to modest changes in the problem input. Further, the robustness model ensures two different predictions can be objectively compared, addressing a shortcoming in prior models. This paper establishes the existence of predictions which satisfy these properties. The paper considers online algorithms with predictions for a network flow allocation problem and the restricted assignment makespan minimization problem. For both problems, three key properties are established: existence of useful predictions that give near optimal solutions, robustness of these predictions to errors that smoothly degrade as the underlying problem instance changes, and we prove high quality predictions can be learned from a small sample of prior instances.