Online Submodular Optimization

Follow this topic Ask about this topic

Latest papers

8 papers0 papers in the last four weeks, against 2 the four weeks before. 0.0% of all new papers.

Consistent Submodular Maximization with Full Foresight
Nov 4, 2026Eric Balkanski, Paul Dütting, Federico Fusco +4Online Submodular Optimization Submodular Optimization
Columbia University · Google Research · Sapienza University of Rome +1
Geometry-Dependent Approximation for Non-Monotone $k$ -Submodular Maximization
Oct 2, 2026Vaneet AggarwalOnline Submodular Optimization Submodular Optimization
Purdue University
Redundancy Meets Synergy: Dependency-aware Expert Selection for MoE via Submodular Optimization
Sep 30, 2026Zheng Lin, Shaoke Fang, Yuxin Zhang +6Submodular Optimization Mixture-of-Experts Pruning
Interdisciplinary Centre for Security, Reliability and Trust, University of Luxembourg, Luxembourg · Department of Computer Science, Peking University, China · Institute of Space Internet, Fudan University, China +4
Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations
Jul 1, 2026Bin Du, Chang Liu, Dingqi Zhu +2Submodular Optimization Distributed Optimization
College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China · School of Artificial Intelligence and Automation at the Huazhong University of Science and Technology, Wuhan, China · School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN 47906, USA
Polyhedral Instability Governs Regret in Online Learning
May 13, 2026Yuetai Li, Fengqing Jiang, Yichen Feng +6Online Convex Optimization Combinatorial Optimization
♣University of Washington · ♢Western Washington University · ♠King Abdulaziz City for Science and Technology ♡HUMAIN
Adaptive Threshold-Driven Continuous Greedy Method for Scalable Submodular Optimization
Apr 3, 2026Mohammadreza Rostami, Solmaz S. KiaOnline Submodular Optimization Submodular Optimization
Department of Mechanical and Aerospace Engineering, University of California Irvine, Irvine, CA 92697
Distributed Online Submodular Maximization under Communication Delays: A Simultaneous Decision-Making Approach
Mar 29, 2026Zirui Xu, Vasileios TzoumasOnline Submodular Optimization Submodular Optimization
Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA
Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization
Feb 22, 2026Zirui Xu, Vasileios TzoumasOnline Submodular Optimization Multi-Agent Coordination
Department of Aerospace Engineering, University of Michigan, Ann Arbor, MI 48109 USA

Nov 4, 2026J/K move · Enter open · S save

Consistent Submodular Maximization with Full Foresight

Eric Balkanski, Paul Dütting, Federico Fusco, Silvio Lattanzi+3

Columbia University · Google Research · Sapienza University of Rome+1

Online Submodular Optimization Submodular Optimization Approximation Algorithms

Open paper AskPDF arXiv

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.