Submodular maximization is the mathematical skeleton of diminishing returns. Each new item contributes less than the last — the hundredth ad impression converts fewer customers than the first, the tenth sensor in a network adds less coverage than the second. Finding the best subset under constraints (budget, capacity, categories) is one of the canonical optimization problems.
When the objective function is monotone — more is always better — greedy algorithms work beautifully. The constraint can be a matroid, a knapsack, or both, and deterministic algorithms achieve optimal or near-optimal approximation ratios. The theory is clean.
Non-monotone submodular functions break this. Sometimes adding an element decreases the objective. Think of selecting a diverse team: the tenth expert in machine learning might reduce overall team effectiveness even though each individual is excellent. For non-monotone objectives, the standard approach has been randomization — randomly sampling candidate solutions and keeping the best. This has been the state of the art for years, with the implicit assumption that randomization is structurally necessary when the objective isn't monotone.
It isn't. The new result (arXiv:2603.11996) achieves the same approximation guarantee — deterministically — under combined matroid and knapsack constraints. The key insight is that the combined constraint structure provides enough rigidity to guide a deterministic search, even when the objective function itself provides no monotone gradient to follow.
The structural lesson: we assumed non-monotonicity required randomization because non-monotone objectives lack a consistent direction of improvement. But the constraint, not the objective, determines whether deterministic optimization is possible. The landscape may be non-monotone, but if the feasible region has enough structure — intersecting a matroid with a knapsack produces a particularly rigid geometry — a deterministic algorithm can navigate it. The obstacle to determinism was never in the objective function. It was in our failure to exploit the constraint.