arXiv preprint ·
Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study nonnegative, non-monotone $k$-submodular maximization with $k\ge2$ labels under support constraints, and show how the certified approximation coefficient improves as the support region permits more uniform selection. For a compact convex down-closed support region $P\subseteq[0,1]^n$, the diagonal level $ζ(P)=\max\{t\in[0,1]:t {\bf 1} \in P\}$ ranges from $ζ=0$, which carries no geometric promise, to $ζ=1$, which is unrestricted support. Our main structural result is a comparator-uniform linearization of the multilinear extension, built from an objective-independent action and a comparator-independent update field. For $k\ge3$, its validity reduces, independently of the number of elements, to four polynomial inequalities of degree at most three in one or two variables, only one of which depends on $k$. Explicit parameter choices give a nondecreasing certified profile $\underlineα_k(ζ)$, in closed form on all of $[0,1]$ when $k=2$. At $ζ=0$ we certify $0.4456\ldots$ for $k=2$ and $0.4541\ldots$ for every $k\ge3$, improving the recent $\sqrt2-1$ guarantee for one matroid or one knapsack, as well as the $1/3$-type guarantees for a fixed number of budgets; at $ζ=1$ we certify $1/2$ for $k=2$, $(\sqrt{17}-3)/2$ for $k=3,4$, and $k/(2k-1)$ for $k\ge5$, whose excess over $1/2$ is of order $1/k$ rather than the previous $1/k^2$. Value-retaining rounding transfers these guarantees to matroid and knapsack constraints, and the same field yields $O(\sqrt T)$ approximate regret online under gradient or post-decision value feedback.
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
A hybrid CNN-adjoint optimization framework for reconstruction of viscoelastic tissue properties in magnetic resonance elastography
Adaptive Bregman Alternating Projections for Feasible Gromov-Wasserstein Learning
Distributed Learning with Selective State Space Models: Architecture-Aware Convergence Analysis
Amortized Score-Hamiltonian Policy Iteration: A Grid-Free Scheme for Relaxed Stochastic Control Problems
Muon Learns Facts Better: Understanding the Role of Spectral Orthogonalization
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.