Curvature Beyond Positivity: Greedy Guarantees for Arbitrary Submodular Functions

ArXi:2605.07902v1 Announce Type: new Submodular functions -- functions exhibiting diminishing returns -- are central to machine learning. When the objective is monotone and non-negative, the greedy algorithm achieves a tight $63\%$ approximation. But many practical objectives incorporate costs that make them negative on some inputs, and all existing multiplicative guarantees require non-negativity.