arXiv preprint ·
An Analytic 0.48-Approximation for Non-Monotone k-Submodular Maximization under a Matroid Constraint
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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\ge2$. 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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Large-Step Last-Iterate Convergence of Random-Reshuffling Stochastic Gradient Descent
When is a better LLM worth paying for? Stochastic Optimization with Switching Mixed-Fidelity Oracles
On the Optimisation Landscape of Overparameterised Weighted MMD
Honesty is the Best Policy ... or is it? Demand Management for Probabilistic Service Options
Quantum-compatible Riemannian conjugate gradient for ground-state preparation
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.