用可学习的预测器提升平滑整数规划求解，保证结果稳定且能高效训练。
Learning-augmented smooth integer programs with PAC-learnable oracles
- 用预测器构建目标函数的线性近似，通过线性规划加取整求解
- 在近稠密场景下仍保持可追踪的近似性能，优于传统方法
- 证明预测器可学习，少量样本即可逼近最优性能
本文研究平滑整数规划的增强学习算法，涵盖最大割（MAX-CUT）和最大k-满足（MAX-k-SAT）等经典问题。提出一种框架，引入预测器构建目标函数的线性代理，通过线性规划求解并经取整得到最终解。关键在于，该框架对预测误差具有稳定且平滑的解质量表现。实验表明，该方法将经典稠密场景下的可解近似推广至近稠密场景。进一步地，突破了预测器存在的假设，证明其在PAC学习意义下可学习：所诱导的算法类具有有界伪维数，因此仅需多项式数量样本即可学习到近最优预期性能的预测器。
原文摘要 · Abstract (English)
This paper investigates learning-augmented algorithms for smooth integer programs, covering canonical problems such as MAX-CUT and MAX-k-SAT. We introduce a framework that incorporates a predictive oracle to construct a linear surrogate of the objective, which is then solved via linear programming followed by a rounding procedure. Crucially, our framework ensures that the solution quality is both consistent and smooth against prediction errors. We demonstrate that this approach effectively extends tractable approximations from the classical dense regime to the near-dense regime. Furthermore, we go beyond the assumption of oracle existence by establishing its PAC-learnability. We prove that the induced algorithm class possesses a bounded pseudo-dimension, thereby ensuring that an oracle with near-optimal expected performance can be learned with polynomial samples.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。