cs.DSNov 15, 2026

Tight Bounds for Non-Monotone Submodular Maximization under a Cardinality Constraint with Constant Recourse

Authors: Vaneet Aggarwal

Organizations: Purdue University, West Lafayette, IN 47907, USA

Abstract

We study the maximization of a nonnegative submodular function under a cardinality constraint when elements arrive one at a time and an algorithm must report a feasible set after every arrival. The recourse of an algorithm is the largest number of insertions and deletions that it makes to the reported set at a single arrival. For every ε>0ε>0, we give an algorithm with recourse O(ε−2)O(ε^{-2}) whose reported set has, at every time, expected value at least 1/4−ε1/4-ε times the largest value of a feasible set of arrived elements. The algorithm evaluates the function polynomially often, and only on sets of arrived elements. We also show that no algorithm with constant recourse achieves a ratio above 1/41/4, even if it knows the function and the arrival order in advance and has unlimited computation, and that any fixed ratio above 1/41/4 requires recourse that grows as a positive power of the cardinality budget. Thus 1/41/4 is the optimal limiting ratio with constant recourse. The previous best ratio with constant recourse was 3−22≈0.1723-2\sqrt2\approx0.172. Our algorithm assigns selection probabilities of at most one half and maintains, as elements arrive, an inequality bounding the value of every feasible set by a multiple of the expected value of a random set drawn with these probabilities; the reported set moves to a rounding of these probabilities through gradual replacements. The upper bound uses a weighted directed graph whose vertices arrive in groups of decreasing sizes.

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