Limit found for efficiently maximizing k-submodular functions
A Tight Oracle Threshold for \(k\)-Submodular Maximization
Data Structures and Algorithms
Summary
Maximizing certain types of complex functions called monotone k-submodular functions is important in some optimization problems. The authors show that if you want to do this maximization very accurately, you will need an exponentially large number of function queries, which is impractical. They identify the exact accuracy threshold beyond which efficient algorithms cannot exist. Their result also aligns with known limits in related non-monotone cases when k is five or more.
What this means in practice
- •For algorithm designers: Prevent wasted effort on creating highly accurate monotone k-submodular maximization algorithms beyond the proven threshold.
- •For optimization engineers: Guide the design of practical heuristics knowing exact approximation barriers for k-submodular maximization problems.
A theory result. No direct application yet.
Authors
Siyuan Chen
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.