Loading
Life sciences · Preprint
arXiv · September 9, 2026
The material analysed did not support any firm read.
This is a theoretical computer science preprint establishing mathematical limits for consistent submodular maximization algorithms. It proves that the best polynomial-time, constant-recourse approximation ratio is bounded at 2−√2 ≈ 0.5858, strictly below the offline guarantee of 1−1/e, and that any improvement requires either exponentially many queries or linear recourse. This work is not applicable to clinical practice or empirical evidence evaluation.
Preprint.
Supremum approximation achievable with polynomially many value queries and worst-case constant recourse is β = 2−√2 ≈ 0.5858, which is less than 1−1/e Randomized algorithm attains β−ε with O(ε−2) changes per insertion for every ε > 0 Any fixed improvement beyond β requires exponentially many queries before one critical insertion or linear recourse of Ω(k) changes
Safety was not reported in the material analysed. Check the source before drawing any conclusion about harm.
The source did not state who this applies to in practice.
This is a theoretical computer science result on algorithmic complexity and approximation bounds, not a clinical or empirical study, and establishes mathematical limits rather than actionable evidence.
Quoted from the source exactly as published.
Graded across the dimensions that decide whether you should act, each from what the source actually supports. There is no single score, and where a dimension was not assessed it says so.
Consistent submodular maximization studies the tradeoff between solution quality and stability when elements arrive over time. For a monotone submodular objective, which models diminishing returns, an algorithm maintains a set of at most $k$ available elements and changes only $O(1)$ elements after each insertion. Dütting et al. [2025] established a tight $2/3$ approximation with unrestricted computation and a polynomial-time $0.51$ approximation. They left open at STOC 2025 whether efficient algorithms can match the offline $1-1/e$ guarantee. We resolve this problem by proving that the supremum approximation achievable with polynomially many value queries and worst-case constant recourse is \[ β=2-\sqrt2\approx0.5858<1-1/e. \] For every $\varepsilon>0$, our randomized algorithm attains $β-\varepsilon$ with $O(\varepsilon^{-2})$ changes per insertion. Any fixed improvement requires exponentially many queries before one critical insertion or linear recourse of $Ω(k)$ changes at that insertion, even with unlimited queries afterwards. This gap quantifies the cost of consistency: the current oracle hides which elements will be needed after an arrival. We also determine the exact curvature-dependent threshold $1-(\sqrt2-1)\vartheta$, attain $1-1/e-\varepsilon$ for weighted coverage with $O(\varepsilon^{-1})$ recourse, and separate the existence of universal future-price certificates from their efficient computation. Our algorithm has a bounded-bit polynomial-time implementation for polynomial-bit rational oracle answers; the lower bound uses only logarithmic-bit rational answers.
Taken from the source record, never inferred. Follow any of these and new work involving them reaches your briefing.