A Tight Oracle Threshold for \(k\)-Submodular Maximization
En palabras de los autores
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.
Resultado principalLimitación que admiten los autores
Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 5 pages