提出数据依赖的上界，更准确评估预算约束下的子模最大化解质量。
Data-dependent Evaluations for Budgeted Submodular Maximization
- 基于实际数据构造新的上界，突破传统最坏情况分析
- 实验验证上界紧致性，在真实数据集上显著优于传统方法
- 适合关注算法性能评估的机器学习与数据挖掘研究者
子模最大化是机器学习与数据挖掘等多个领域的重要基础。由于该问题为NP难，现有算法分析通常仅提供悲观的最坏情况近似因子，难以评估具体实例中解与最优解的接近程度。本文提出针对带背包约束的子模最大化的新数据依赖上界。理论上证明这些上界严格优于最优解，并通过真实数据集实验验证其在评估解质量上的优势，显著提升了对算法输出解的可信度判断能力。
原文摘要 · Abstract (English)
Submodular maximization is an important building block for developing algorithms in many areas such as machine learning and data mining. Due to the NP-hardness of the problem, analysis of submodular maximization algorithms typically provides pessimistic worst-case approximation factors only. It is not easy to evaluate how close a produced solution is to an optimal one for a given problem instance. In this paper, we develop new data-dependent upper bounds for submodular maximization with a knapsack constraint. We theoretically prove that they dominate the optimal solution and empirically demonstrate their advantages in certifying how close to optimal a solution is through experiments with real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。