用预测改进经典算法的近似率，不增加时间开销。
Approximation Algorithms for Combinatorial Optimization with Predictions
- 基于预测构建近似算法，输入为可行子集选择问题。
- 预测准确时达最优，误差增大时近似率平滑下降。
- 适用于顶点覆盖、斯坦纳树等难题，适合追求高效解的场景。
我们系统性地研究如何利用预测来提升经典算法的近似保证，且不增加运行时间。针对一类要求选取输入项的可行子集以最小化（或最大化）总权重的经典优化问题，提出一种通用方法。该方法可产生简单（近）线性时间算法，适用于顶点覆盖、斯坦纳树、最小权完美匹配、背包问题和团问题等。当提供完美预测时，算法能产出最优解；预测误差越大，近似比越差，但呈平滑退化。在预测误差足够小时，可获得在给定时间约束下无法达到的近似保证，这在许多问题（如上述问题的NP难性和APX难性）中已得到体现。尽管我们证明该方法对这类问题整体是最优的，但个别问题若具备特定结构，仍可能进一步优化；我们在斯坦纳树问题上展示了这一点。最后进行了实证评估。
原文摘要 · Abstract (English)
We initiate a systematic study of utilizing predictions to improve over approximation guarantees of classic algorithms, without increasing the running time. We propose a systematic method for a wide class of optimization problems that ask to select a feasible subset of input items of minimal (or maximal) total weight. This gives simple (near-)linear time algorithms for, e.g., Vertex Cover, Steiner Tree, Min-Weight Perfect Matching, Knapsack, and Clique. Our algorithms produce optimal solutions when provided with perfect predictions and their approximation ratios smoothly degrade with increasing prediction error. With small enough prediction error we achieve approximation guarantees that are beyond reach without predictions in the given time bounds, as exemplified by the NP-hardness and APX-hardness of many of the above problems. Although we show our approach to be optimal for this class of problems as a whole, there is a potential for exploiting specific structural properties of individual problems to obtain improved bounds; we demonstrate this on the Steiner Tree problem. We conclude with an empirical evaluation of our approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。