arXiv:2611.13575 · v1

Greedy+Singleton for knapsack-constrained monotone submodular maximization has approximation ratio exactly $β^\star \approx 0.42944$

首次提交 2026-11-10 12:45

版本更新 2026-11-10 12:45

雷达观测 2026-11-11 11:04

摘要

Greedy+Singleton is the textbook heuristic for monotone submodular maximization under a knapsack constraint: it returns the better of the cost-benefit greedy set and the best single item. Its worst-case approximation ratio, known only to lie in $[0.427, 0.42945]$ (Feldman-Nutov-Shoham; Kulik-Schwartz-Shachnai), is exactly an explicit constant $β^\star\approx 0.42944$. In the extremal instances, many cheap "filler" items wear down the value of two large optimal items while greedy spends the budget, until neither fits. This picture gives a sharper factor-revealing relaxation; we bound it analytically near the extremal parameters, up to finitely many interval-arithmetic checks, and certify it elsewhere by an exact branch-and-bound. The matching bad instances are tie-free and checkable by hand. For the version that stops at the first item that does not fit, Wolsey's bound $1-e^{-β_W}\approx 0.35780$, where $e^{β_W}=2-β_W$, is tight; Wolsey stated this for his variant without giving the instances, and we give an explicit family with no ties that also covers comparison with the best feasible singleton. The CELF rule also has ratio exactly $β^\star$.

作者备注：26 pages, 4 figures. Code and certificates: https://doi.org/10.5281/zenodo.24023723