# Metadata

- Title: Improved Randomized Algorithm for k-Submodular Function Maximization
- Authors: Hiroki Oshima
- Year: 2021
- Venue: SIAM Journal on Discrete Mathematics 35(1):1-22; inbox file is the 2019 arXiv preprint
- Primary group: k-submodular
- Secondary tags: non-monotone, unconstrained, randomized, oracle-model, journal-version
- Problem: unconstrained maximization of a nonnegative non-monotone k-submodular function in the value-oracle model
- Main guarantee: improves the non-monotone unconstrained randomized approximation line beyond 1/2, giving `(k^2 + 1) / (2k^2 + 1)` for `k >= 3` and the sharper special-case ratio `(sqrt(17) - 3) / 2` for `k = 3`
- Key techniques: refined one-step analysis of the standard randomized assignment framework, stronger handling of the unique negative comparison marginal, ordered-marginal probability design, special-case optimization for `k = 3`
- Status: processed-deep
- Tags: #k-submodular #unconstrained #non-monotone #randomized #oracle-model #maximization
- Inbox source: inbox/1907.12942v1.pdf