# Metadata

- Title: On maximizing a monotone k-submodular function subject to a matroid constraint
- Authors: Shinsaku Sakaue
- Year: 2016
- Venue: arXiv preprint (`arXiv:1607.07957v3`, August 22, 2016)
- Primary group: k-submodular
- Secondary tags: matroid, monotone, greedy, constrained-maximization
- Problem: monotone k-submodular maximization under a matroid constraint on the support
- Main guarantee: a simple greedy algorithm gives a `1 / 2`-approximation for monotone k-submodular maximization subject to a matroid constraint, in `O(M |E| (MO + k EO))` oracle time, where `M` is the basis size
- Key techniques: greedy element-label selection, basis exchange inside a matroid, orthant-submodular comparison, monotonicity, and step-by-step hybrid optimal solutions
- Status: processed-deep
- Tags: #k-submodular #matroid #monotone #greedy #approximation #arXiv
- Inbox source: inbox/1607.07957v3.pdf