---
title: "Consistent Submodular Maximization with Full Foresight"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.06223v1"
permalink: "https://feed.astralor.com/items/itm_18eb9966f697b0937ddc463a"
published: "2026-11-04T09:32:32.000Z"
score: 59
channel: "tech"
tags: ["RAG","Consistent Submodular Maximization","Full Foresight Online","Online","For"]
---

# Consistent Submodular Maximization with Full Foresight

## At a glance

Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental question that separates consistency fr…

## Key points

- Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes.
- We ask a fundamental question that separates consistency from the other two: what does solution stability cost when the entire future is known and computation is unlimited?
- We answer this question for monotone submodular maximization, where an algorithm must maintain a solution of at most $k$ arrived elements, with a constant number of changes per step.

## Full text

Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental question that separates consistency from the other two: what does solution stability cost when the entire future is known and computation is unlimited? We answer this question for monotone submodular maximization, where an algorithm must maintain a solution of at most $k$ arrived elements, with a constant number of changes per step. We determine the optimal approximation thresholds: $3/4$ for deterministic algorithms and $ξ^\star \approx 0.7942$ for randomized algorithms. For every $\varepsilon>0$, we get within $\varepsilon$ of these thresholds with worst-case recourse polynomial in $1/\varepsilon$, independent of $k$ and the stream length. We prove matching impossibility results even for coverage functions. We attain the sharp bounds by optimally balancing two opposing forces: preparing for future arrivals and protecting the current solution. For randomized algorithms, we use addition robustness against prefixes of the known future, which we analyze tightly via an interval-selection problem. For deterministic algorithms, we introduce certificates, paths in a fractional relaxation that maintain high value, which we round into an update schedule.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_18eb9966f697b0937ddc463a