---
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

## 速览

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…

## 关键点

- 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.

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_18eb9966f697b0937ddc463a