论文标题
在线匹配，流量和负载平衡的可学习且实例的预测
Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing
论文作者
论文摘要
我们提出了一个新的模型，用于通过要求正式学习和实例强大的实例来增强算法的预测。可学习性确保可以从合理数量的过去数据中有效构建预测。实例鲁棒性可确保预测对问题输入的适度变化具有鲁棒性，在这种情况下，更改的度量可能是特定于问题的。实例鲁棒性坚持性能的平稳降解，这是变化的函数。理想情况下，性能永远不会比最差的范围差。这也允许客观比较预测。 我们设计了在线算法，可以预测网络流分配问题和限制任务使PAN最小化。对于这两个问题，都建立了两个关键属性：可以从一小部分先前实例中学习高质量的预测，并且这些预测对随着潜在问题实例的变化而平稳降低的错误是可靠的。
We propose a new model for augmenting algorithms with predictions by requiring that they are formally learnable and instance robust. Learnability ensures that predictions can be efficiently constructed from a reasonable amount of past data. Instance robustness ensures that the prediction is robust to modest changes in the problem input, where the measure of the change may be problem specific. Instance robustness insists on a smooth degradation in performance as a function of the change. Ideally, the performance is never worse than worst-case bounds. This also allows predictions to be objectively compared. We design online algorithms with predictions for a network flow allocation problem and restricted assignment makespan minimization. For both problems, two key properties are established: high quality predictions can be learned from a small sample of prior instances and these predictions are robust to errors that smoothly degrade as the underlying problem instance changes.
