arXiv preprint ·
A Tight Oracle Threshold for \(k\)-Submodular Maximization
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We prove that, for every \(\varepsilon>0\), a \((\frac{k}{2k-1}+\varepsilon)\)-approximation algorithm for maximizing monotone \(k\)-submodular functions requires exponentially many value-oracle queries. This improves the \(\frac{k+1}{2k}\) oracle bound of Iwata, Tanigawa, and Yoshida. Their \(\frac{k}{2k-1}\)-approximation algorithm therefore gives the exact threshold in the monotone setting. For \(k\ge5\), our bound also matches, up to an arbitrarily small loss, Aggarwal's recent approximation guarantee for non-monotone \(k\)-submodular maximization.
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
Hadamard Transforms for Dimension Reduction
Approximating Directed Telephone Multicast
Exact minimum Birkhoff decompositions of doubly stochastic matrices with finite precision
A 55-Addition Rank-23 Scheme for $3\times3$ Matrix Multiplication via Exact Two-Sided Minimization
Integer Programing: An Algorithm with Exponent Linear in the Dimension
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.