Improved Approximation Algorithms for k-Submodular Function Maximization

Satoru Iwata, Shin-ichi Tanigawa, Yuichi Yoshida

Abstract

This paper presents a polynomial-time $1/2$-approximation algorithm for maximizing nonnegative $k$-submodular functions. This improves upon the previous $\max\{1/3, 1/(1+a)\}$-approximation by Ward and Živný (SODA'14), where $a=\max\{1, \sqrt{(k-1)/4}\}$. We also show that for monotone $k$-submodular functions there is a polynomial-time $k/(2k-1)$-approximation algorithm while for any $\varepsilon>0$ a $((k+1)/2k+\varepsilon)$-approximation algorithm for maximizing monotone $k$-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skew-bisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.

Introduction

Submodular function maximization is a cornerstone of combinatorial optimization, capturing the "law of diminishing returns" prevalent in economics, machine learning, and network design. Traditionally, submodularity is defined over a single set: adding an element to a smaller set yields a greater marginal gain than adding it to a larger one. However, many real-world scenarios require assigning elements to multiple categories or agents. This leads to the concept of $k$-submodularity.

A function $f: (k+1)^V \to \mathbb{R}$ is $k$-submodular if it models diminishing returns across $k$ disjoint sets. This structure is particularly relevant in resource allocation problems, such as the submodular welfare problem, where $k$ agents compete for a set of items $V$. Despite its utility, the approximation landscape for $k$-submodular functions has historically lagged behind standard submodular maximization. This work bridges that gap, achieving the "natural" $1/2$ approximation threshold.

The Randomized Greedy Framework

The primary contribution of this research is a randomized greedy algorithm that processes elements of the ground set $V$ sequentially. For each element, the algorithm evaluates the marginal gain of adding it to each of the $k$ possible sets.

The core innovation lies in the selection strategy. Previous approaches often relied on simple greedy choices or limited randomization, which capped the approximation ratio at approximately $1/3$. The authors introduce a novel probability distribution derived from a geometric sequence to decide which set (if any) an element should be assigned to.

1. General k-Submodular Maximization

For non-negative $k$-submodular functions, the algorithm uses a carefully balanced distribution to ensure the expected gain at each step is sufficient to reach a $1/2$-approximation. This ratio is significant because it matches the best possible result for standard (1-submodular) unconstrained maximization in the value oracle model.

2. Monotone k-Submodular Maximization

In the monotone case—where adding an element to a set never decreases the function's value—the authors provide a $k/(2k-1)$-approximation. For the specific case of $k=2$ (bisubmodular functions), this results in a $2/3$ approximation ratio.

Hardness and Asymptotic Tightness

To evaluate the optimality of these algorithms, the authors employ query complexity analysis. Using Yao’s min-max principle, they establish that any algorithm attempting to achieve an approximation ratio better than $(k+1)/2k + \varepsilon$ would require an exponential number of function evaluations (queries).

This hardness result is particularly revealing when considering the limit as $k$ increases. As $k \to \infty$, the term $(k+1)/2k$ approaches $1/2$. This implies that the $1/2$-approximation algorithm for general $k$-submodular functions is asymptotically tight. For large $k$, no polynomial-time algorithm can perform better than the one presented here.

Theoretical Insights: Orthant Submodularity

The paper clarifies the mathematical nature of $k$-submodularity by decomposing it into two properties:

  • Orthant Submodularity: Diminishing returns within a specific assignment.
  • Pairwise Monotonicity: A technical condition governing how gains relate across different sets.

By viewing $k$-submodular maximization as a middle ground between standard submodularity and partition matroid constraints, the authors were able to extend their techniques to skew-bisubmodular functions. These are a recent generalization of bisubmodularity, and this work provides the first constant-factor approximation algorithms for them.

Conclusion

This work establishes $1/2$ as the fundamental approximation threshold for $k$-submodular maximization, mirroring the landscape of standard submodular functions. While the results are theoretically optimal for large $k$, a small gap remains for the monotone case at low values of $k$ (between the $k/(2k-1)$ algorithmic result and the $(k+1)/2k$ hardness bound). Future research may explore whether these ratios can be improved under specific constraints, such as knapsack or general matroid constraints, within the value oracle model.

Summary updated

Abstract

This paper presents a polynomial-time $1/2$-approximation algorithm for maximizing nonnegative $k$-submodular functions. This improves upon the previous $\max\{1/3, 1/(1+a)\}$-approximation by Ward and \v{Z}ivn\'y~(SODA'14), where $a=\max\{1, \sqrt{(k-1)/4}\}$. We also show that for monotone $k$-submodular functions there is a polynomial-time $k/(2k-1)$-approximation algorithm while for any $\varepsilon>0$ a $((k+1)/2k+\varepsilon)$-approximation algorithm for maximizing monotone $k$-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skew-bisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.
BibTeX
@inproceedings{iwata2016improved,
  author = {Satoru Iwata and Shin-ichi Tanigawa and Yuichi Yoshida},
  title = {{Improved Approximation Algorithms for k-Submodular Function Maximization}},
  booktitle = {SODA},
  year = {2016},
  doi = {10.1137/1.9781611974331.ch30},
}
Figure