Id: arxiv/2611.11124 Url: https://arxiv.org/abs/2611.11124 Tags: cs.DS, cs.LG, math.OC Score: 0 Title: Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead Domain: cs.DS Source: arxiv Authors: Vaneet Aggarwal Reviews: 0 Subject: cs.DS Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-11-08 Page: https://delphi.science/r/arxiv/2611.11124 Elements arrive one at a time, and after each arrival an algorithm holds a set of at most $k$ arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that $k$ arrived elements can achieve. The recourse of an update is the number of elements inserted into or removed from the held set, and we require it to be bounded independently of $k$ and of the number $n$ of arrivals. With evaluations only on sets of arrived elements and polynomially many of them, the best ratio a randomized algorithm can achieve is $2-\sqrt{2}\approx0.5858$. We…