# Metadata

- Title: Improved Approximation Algorithms for k-Submodular Function Maximization
- Authors: Satoru Iwata, Shin-ichi Tanigawa, Yuichi Yoshida
- Year: 2015
- Venue: later appeared in SODA 2016; arXiv preprint (`arXiv:1502.07406v1`, February 26, 2015)
- Primary group: k-submodular
- Secondary tags: maximization, randomized-greedy, monotone, hardness, skew-bisubmodular
- Problem: unconstrained maximization of nonnegative k-submodular functions, plus the monotone special case and skew-bisubmodular extensions
- Main guarantee: gives a randomized `1 / 2`-approximation for nonnegative k-submodular maximization, a `k / (2k - 1)`-approximation for monotone objectives, and proves that any `((k + 1) / (2k) + eps)`-approximation for monotone k-submodular maximization needs exponentially many value queries
- Key techniques: randomized greedy with geometric probabilities, orthant-submodular and pairwise-monotone local inequalities, Feige-Mirrokni-Vondrak-style symmetry hardness, and skew-bisubmodular probability tuning
- Status: processed-deep
- Tags: #k-submodular #maximization #randomized-greedy #monotone #hardness #skew-bisubmodular #SODA #arXiv
- Inbox source: inbox/1502.07406v1.pdf