Learning-Augmented Algorithms: Guarantees, Construction Mechanisms, and System-Level Implications
arXiv:2609.04787v1 发布一篇关于学习增强算法的综述，该文章综合了预测接口、误差度量及一致性 - 鲁棒性权衡，并涵盖了在线优化、缓存、学习数据结构、图问题及机制设计领域的五种代表性构建机制。文章通过定理层面的正交轴区分了已实现的上界与匹配的渐近依赖关系，将形式保证与实证系统证据分离，并明确处理了预测成本、反馈及组合问题。综述提出了有限端到端推理的充分条件，并 delineated 了成本感知预测、内生误差、语义预测器及基准测试等开放问题。