cs.DSNov 8, 2026

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

Authors: Vaneet Aggarwal

Organizations: Purdue University

Abstract

Elements arrive one at a time, and after each arrival an algorithm holds a set of at most kk arrived elements. Its goal is a held set whose value under a monotone submodular function is close to the best value that kk 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 kk and of the number nn 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−2≈0.58582-\sqrt{2}\approx0.5858. We show that seeing future arrivals raises the best ratio for polynomially many evaluations to 1−1/e≈0.63211-1/e\approx0.6321, for deterministic and for randomized algorithms; no algorithm with polynomially many evaluations exceeds 1−1/e1-1/e, even when all elements are available at once. For every ε>0\varepsilon>0, a deterministic algorithm that sees the next ⌈εk/3⌉\lceil\varepsilon k/3\rceil arrivals keeps a set of value at least 1−1/e−ε1-1/e-\varepsilon times the optimum at every time, changes O(ε−3)O(\varepsilon^{-3}) elements per arrival and makes (n+1)O(ε−2)(n+1)^{O(\varepsilon^{-2})} evaluations. With the whole arrival sequence known in advance, a deterministic algorithm attains the same ratio with O(ε−2)O(\varepsilon^{-2}) changes per arrival. A randomized algorithm with the same short lookahead makes O(n2k)O(n^2k) evaluations, changes O(ε−2)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.

Figures & tables

Explore similar work

CardsList
  1. Consistent Submodular Maximization with Full Foresight

    Nov 4, 2026Eric Balkanski, Paul Dütting, Federico Fusco +4Online Submodular OptimizationSubmodular Optimization

  2. A General Framework for Dynamic Consistent Submodular Maximization

    Jun 3, 2026Paul Dütting, Federico Fusco, Silvio Lattanzi +3Submodular OptimizationApproximation Algorithms