PreprintarXiv licencearXiv
An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
Abstract
We give a randomized polynomial-time $0.48$-approximation for maximizing a nonnegative non-monotone k-submodular function under a matroid constraint, for every k≥2. The algorithm combines a top-two label rule with a nested-chain potential and maximum-weight matroid bases. Its analysis reduces the approximation guarantee to a one-dimensional time allocation: a uniform local lower bound leads to a linear differential equation, concavity closes the remaining interval, and two elementary budgets complete the proof. A strict saving in the time budget absorbs sampling and discretization errors, yielding the exact $0.48$ guarantee in the value-oracle model.
Related
- A Deterministic $0.401$-Approximation for Non-monotone Submodular Maximization under Matroid Constraints
- Geometry-Dependent Approximation for Non-Monotone k-Submodular Maximization
- 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{wang2026analytic,
title = {{An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint}},
author = {Zizong Wang and Yibo Wang and Wenguo Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.20140},
eprint = {2610.20140},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.20140},
}
RIS
TY - UNPB
TI - An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
AU - Zizong Wang
AU - Yibo Wang
AU - Wenguo Yang
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.20140
UR - https://arxiv.org/abs/2610.20140
AB - We give a randomized polynomial-time $0.48$-approximation for maximizing a nonnegative non-monotone k-submodular function under a matroid constraint, for every k≥2. The algorithm combines a top-two label rule with a nested-chain potential and maximum-weight matroid bases. Its analysis reduces the approximation guarantee to a one-dimensional time allocation: a uniform local lower bound leads to a linear differential equation, concavity closes the remaining interval, and two elementary budgets complete the proof. A strict saving in the time budget absorbs sampling and discretization errors, yielding the exact $0.48$ guarantee in the value-oracle model.
ER -