Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead

Vaneet AggarwalarXiv 2026 · arXiv

This paper, authored by Vaneet Aggarwal from Purdue University, tackles a fundamental challenge in online optimization: how to maintain a high-quality solution for submodular maximization as data arrives sequentially, without constantly overhauling your current selection.

TL;DR

The paper proves that a small amount of "lookahead" (seeing a few future elements) allows online algorithms to reach the optimal $1-1/e$ approximation ratio for submodular maximization with constant recourse. It introduces new deterministic and randomized algorithms that achieve this "holy grail" ratio using only polynomially many function evaluations.

What Problem Does This Paper Address?

Submodular maximization is the mathematical backbone of problems involving "diminishing returns," such as sensor placement, document summarization, or influence maximization in social networks. In the consistent online setting, elements arrive one by one, and an algorithm must maintain a set of at most $k$ elements.

The challenge is two-fold:

  1. Recourse: We want "consistent" solutions, meaning we shouldn't swap out too many elements at each step. Ideally, the number of changes (recourse) should be independent of the total number of elements ($n$) and the budget ($k$).
  2. Query Complexity: We only have access to the objective function $f$ through a "value oracle" (we can ask for the value of a set). We want to find a good solution using only a polynomial number of these queries.

Previous work showed that without knowing the future, the best possible approximation ratio for randomized algorithms with polynomial queries is $2 - \sqrt{2} \approx 0.5858$. This paper asks: Can a short lookahead bridge the gap to the optimal $1-1/e \approx 0.6321$ ratio?

Summary of the three algorithms introduced in the paper, comparing their guarantees, lookahead requirements, query complexity, and recourse.

Methods

The author introduces a "checkpoint" framework where the algorithm periodically updates its "core" set of elements. The key innovations are:

  • Simultaneous Greedy (Algorithm 1): A novel greedy variant that doesn't just optimize for one target set. Instead, it provides a mathematical guarantee for every possible "future prefix"—meaning the solution remains robust regardless of how many future elements from the lookahead window are actually considered.
  • Checked Transitions (Algorithm 2): For deterministic algorithms, moving from an old set to a new one is risky because intermediate sets might be poor. The author developed a "path-building" tool that uses exhaustive batch searches to find "compensating" elements, ensuring every single step in a transition maintains a high value.
  • Optimum Bounding: Since the true optimal value ($OPT$) is unknown, the deterministic algorithm uses "failed searches" for better sets to mathematically prove upper bounds on $OPT$, which it then uses to decide exactly when to trigger a transition.

Datasets

This is a theoretical paper focused on algorithmic complexity and approximation guarantees. It does not use empirical datasets but evaluates algorithms against the standard Value Oracle Model for monotone submodular functions.

Key Insights and Ideas

  • Lookahead is the "Secret Sauce": By seeing just the next $\approx \varepsilon k$ elements, the algorithm can anticipate shifts in the optimal set. This foresight is what allows it to break the $2 - \sqrt{2}$ barrier that limits non-foresight algorithms.
  • Linear Lookahead is Necessary: The paper proves that to beat the $0.5858$ ratio, the lookahead window must grow linearly with the budget $k$. Constant lookahead isn't enough.
  • Deterministic vs. Randomized: Randomized algorithms are "lazier"—they can hide transitions within a random time window. Deterministic algorithms are much harder to design because they must prove that every intermediate set held during a transition is high-quality.

Key Results

The paper presents three main algorithms, summarized in the table below:

Summary of the three algorithms introduced in the paper, comparing their guarantees, lookahead requirements, query complexity, and recourse.
  • Deterministic Algorithm: Achieves a $(1 - 1/e - \varepsilon)$ ratio with $O(\varepsilon^{-3})$ recourse. It requires $(n+1)^{O(\varepsilon^{-2})}$ queries, meaning the query count is polynomial for any fixed accuracy $\varepsilon$.
  • Randomized Algorithm: Achieves the same ratio in expectation with slightly better recourse ($O(\varepsilon^{-2})$) and a query complexity of $O(n^2k)$ that doesn't depend on $\varepsilon$ in the exponent.
  • Optimality: The paper proves that $1-1/e$ is the absolute upper bound for any algorithm making polynomially many queries, even with full foresight. Thus, these algorithms are optimal.

Limitations and Future Work

  • Query Exponent: For the deterministic algorithm, the number of queries has $\varepsilon^{-2}$ in the exponent of $n$. While technically polynomial, this could be computationally expensive for very high precision (small $\varepsilon$).
  • Recourse Gap: There is a slight gap between the deterministic recourse ($O(\varepsilon^{-3})$) and the randomized recourse ($O(\varepsilon^{-2})$). Whether the deterministic version can be improved remains an open question.
  • Lookahead Size: While the lookahead is "short" relative to the total stream, it still scales with $k$. Finding ways to reduce this further while maintaining the $1-1/e$ ratio is a potential future direction.

Summary updated

Abstract

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 show that seeing future arrivals raises the best ratio for polynomially many evaluations to $1-1/e\approx0.6321$, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds $1-1/e$, even when all elements are available at once. For every $\varepsilon>0$, a deterministic algorithm that sees the next $\lceil\varepsilon k/3\rceil$ arrivals keeps a set of value at least $1-1/e-\varepsilon$ times the optimum at every time, changes $O(\varepsilon^{-3})$ elements per arrival and makes $(n+1)^{O(\varepsilon^{-2})}$ evaluations. With the whole arrival sequence known in advance, a deterministic algorithm attains the same ratio with $O(\varepsilon^{-2})$ changes per arrival. A randomized algorithm with the same short lookahead makes $O(n^2k)$ evaluations, changes $O(\varepsilon^{-2})$ elements per arrival, and attains the same ratio in expectation at each fixed time. The main tool is a greedy algorithm with an explicit guarantee for each of its partial solutions combined with each initial segment of the known future arrivals. A second tool moves between two such solutions one element at a time while keeping the value high, and the deterministic algorithm times each move using upper bounds on the optimum from failed searches.
BibTeX
@misc{aggarwal2026optimal,
  author = {Vaneet Aggarwal},
  title = {{Optimal Polynomial-Query Approximation for Consistent Submodular Maximization with Short Lookahead}},
  year = {2026},
  eprint = {2611.11124},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.11124},
}
Figure