Geometry-Dependent Approximation for Non-Monotone k-Submodular Maximization
Abstract
We study the maximization of a nonnegative k-submodular function, not assumed monotone, in which each of n elements receives one of k≥2 labels or stays unselected and the selected elements must satisfy a constraint. For a compact convex down-closed region P⊆[0,1]n of fractional selection vectors, the diagonal level ζ(P)=max{t∈[0,1]:t(1,…,1)∈ P} is the largest selection probability that can be given to all elements at once; it equals r/n for a uniform matroid of rank r, and ζ(P)=1 means that the constraint is vacuous. We give approximation coefficients that increase continuously with ζ. They come from one inequality for the multilinear extension of the objective: the algorithm computes an action without querying the objective, and objective feedback gives a comparator-independent update direction. For k≥3, feasibility of the action reduces to three polynomial inequalities in one variable; for k=2 the profile is closed form. At ζ=0 the coefficients are 0.4456… for k=2 and 0.4541… for every k≥3. For every finite k≥3 they reach 1/2 above an explicit level, which is 0.4026… for k=3,4,5, and at ζ=1 they reach 1/2 for k=2, (√(17)−3)/2 for k=3,4, and k/(2k−1) for k≥5. Online linear optimization gives O(√T) approximate regret, with gradient feedback or with value queries made after each action. The coefficients carry over to matroids, with expected and high-probability guarantees, and to any fixed number of knapsacks: the zero-level coefficients hold on every instance, and the larger ones when items are small or when prefix enumeration keeps the diagonal level on one branch. For one budget the enumeration exponent is O(1/ε).
Related
- An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
- A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints
- Online Non-Monotone DR-Submodular Maximization Matching the Offline $0.401$ Factor
- Dec-BFTRL: Squre-Root Regret for Decentralized Online Upper-Linearizable Optimization under Separation Access with Application to Continuous Submodular Maximization
- On Exact Dual and Mixed-Integer Reformulations for Finite Horizon Markov Decision Processes with Submodular Revenue Maximization
BibTeX
@misc{aggarwal2026geometrydependent,
title = {{Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization}},
author = {Vaneet Aggarwal},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04049},
eprint = {2610.04049},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04049},
}
RIS
TY - UNPB
TI - Geometry-Dependent Approximation for Non-Monotone k-Submodular Maximization
AU - Vaneet Aggarwal
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.04049
UR - https://arxiv.org/abs/2610.04049
AB - We study the maximization of a nonnegative k-submodular function, not assumed monotone, in which each of n elements receives one of k≥2 labels or stays unselected and the selected elements must satisfy a constraint. For a compact convex down-closed region P⊆[0,1]^n of fractional selection vectors, the diagonal level ζ(P)=max{t∈[0,1]:t(1,…,1)∈ P} is the largest selection probability that can be given to all elements at once; it equals r/n for a uniform matroid of rank r, and ζ(P)=1 means that the constraint is vacuous. We give approximation coefficients that increase continuously with ζ. They come from one inequality for the multilinear extension of the objective: the algorithm computes an action without querying the objective, and objective feedback gives a comparator-independent update direction. For k≥3, feasibility of the action reduces to three polynomial inequalities in one variable; for k=2 the profile is closed form. At ζ=0 the coefficients are 0.4456… for k=2 and 0.4541… for every k≥3. For every finite k≥3 they reach 1/2 above an explicit level, which is 0.4026… for k=3,4,5, and at ζ=1 they reach 1/2 for k=2, (√(17)−3)/2 for k=3,4, and k/(2k−1) for k≥5. Online linear optimization gives O(√T) approximate regret, with gradient feedback or with value queries made after each action. The coefficients carry over to matroids, with expected and high-probability guarantees, and to any fixed number of knapsacks: the zero-level coefficients hold on every instance, and the larger ones when items are small or when prefix enumeration keeps the diagonal level on one branch. For one budget the enumeration exponent is O(1/ε).
ER -