SOURCE-LINKED INTELLIGENCE

Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor

arXiv · AI, language, vision and robotics · article · Sep 2, 2026 · UTC

We study online maximization of nonnegative, non-monotone DR-submodular functions over compact convex down-closed subsets of the $d$-dimensional unit cube. The best known constructive offline approximation factor is $0.401$ under the corresponding meta-solvability assumptions, whereas comparable adversarial online guarantees had remained at $1/e$. We show that this factor is also achievable online. In the post-decision full-information value-oracle model, our algorithm attains factor $0.401$ with sublinear approximate regret when oracle feedback is conditionally unbiased and bounded. The onlin

Read original source ↗ Open in workspace

recordType

paper

region

Global