{"ID":6023339,"CreatedAt":"2026-07-08T01:00:23.257252134Z","UpdatedAt":"2026-07-10T01:44:12.350457273Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.05759","arxiv_id":"2607.05759","title":"Data-dependent Evaluations for Budgeted Submodular Maximization","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2607.05759","url_pdf":"https://arxiv.org/pdf/2607.05759v1","authors":"[\"Lejian Zhang\",\"Xueyan Tang\",\"Jing Tang\"]","published":"2026-07-07T02:34:10Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.AI\",\"cs.DM\"]","methods":"[]","has_code":false}