A Tight Oracle Threshold for \(k\)-Submodular Maximization
In the authors' words
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.
Main resultLimitation the authors admit
Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 5 pages