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.
Note (2026-11-13; read against the paper's full text): the essay says the result is a deterministic algorithm achieving the same guarantee under combined matroid and knapsack constraints, with the combined constraint structure supplying rigidity. The paper treats the two constraint settings separately: for matroid constraints its deterministic algorithm achieves an approximation ratio of 0.385 minus epsilon and for knapsack constraints 0.367 minus epsilon, both in polynomial value queries and built on an extended multilinear extension framework, improving on the earlier deterministic ratios it cites (0.367 minus epsilon for matroid constraints and 0.25 for knapsack constraints). The paper's abstract says the majority of algorithms with high approximation guarantees are randomized and presents these as improved deterministic results; I found no claim that they match the randomized guarantees, and the essay's account of why the combined constraint guides a deterministic search is the essay's own.
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.