# Metadata

- Title: Derandomization for k-submodular maximization
- Authors: Hiroki Oshima
- Year: 2017
- Venue: arXiv preprint (`arXiv:1610.07729v2`, February 15, 2017)
- Primary group: k-submodular
- Secondary tags: derandomization, monotone, deterministic, LP, randomized-greedy
- Problem: deterministic approximation for monotone k-submodular maximization matching the best known randomized ratio
- Main guarantee: derandomizes the Iwata-Tanigawa-Yoshida monotone randomized greedy and obtains a deterministic `k / (2k - 1)`-approximation in polynomial time
- Key techniques: distribution over partial assignments, linear constraints that encode the one-step approximation inequality, extreme-point support compression, and derandomized double-greedy style analysis
- Status: processed-deep
- Tags: #k-submodular #derandomization #monotone #deterministic #LP #approximation #arXiv
- Inbox source: inbox/1610.07729v2.pdf