用预测信息突破经典图算法的近似瓶颈，提升多个难解问题的求解效果。
Improved Approximations for Hard Graph Problems using Predictions
- 基于边的预测框架，每条边提供两个端点是否在最优解中的线索
- 在弱预测下仍能打破传统近似比上限，实现多类问题的新最优解
- 适合关注机器学习与组合优化融合的算法研究者
我们通过引入预测（例如来自历史数据的预判）设计了改进的近似算法，用于解决NP难图问题。预测模型基于Cohen-Addad等人（NeurIPS 2024）提出的ε-预测框架，并扩展为基于边的版本：每条边提供两个比特信息，分别预测其两个端点是否属于最优解。即使每个比特仅与真实解有ε相关性，这些信息仍足以打破标准设置下的近似障碍。我们为最大割（MaxCut）、顶点覆盖（Vertex Cover）、集合覆盖（Set Cover）和最大独立集（Maximum Independent Set）等众多问题开发了具有更优近似比的算法。这些算法共享统一思路：对高度顶点使用预测来满足约束，对低度顶点则不依赖预测，再精细组合结果。
原文摘要 · Abstract (English)
We design improved approximation algorithms for NP-hard graph problems by incorporating predictions (e.g., learned from past data). Our prediction model builds upon and extends the $\varepsilon$-prediction framework by Cohen-Addad, d'Orsi, Gupta, Lee, and Panigrahi (NeurIPS 2024). We consider an edge-based version of this model, where each edge provides two bits of information, corresponding to predictions about whether each of its endpoints belong to an optimal solution. Even with weak predictions where each bit is only $\varepsilon$-correlated with the true solution, this information allows us to break approximation barriers in the standard setting. We develop algorithms with improved approximation ratios for MaxCut, Vertex Cover, Set Cover, and Maximum Independent Set problems (among others). Across these problems, our algorithms share a unifying theme, where we separately satisfy constraints related to high degree vertices (using predictions) and low-degree vertices (without using predictions) and carefully combine the answers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。