# Metadata

- Title: Fast algorithms for k-submodular maximization subject to a matroid constraint
- Authors: Shuxian Niu, Qian Liu, Yang Zhou, Min Li
- Year: 2023
- Venue: arXiv preprint, July 26, 2023; journal venue to verify
- Primary group: k-submodular
- Secondary tags: matroid, total-size, monotone, non-monotone, threshold-decreasing, query-efficient
- Problem: fast value-oracle algorithms for k-submodular maximization under a matroid constraint, with total-size constraint as a uniform-matroid corollary
- Main guarantee: gives a threshold-decreasing algorithm with `(1/2 - epsilon)` approximation for monotone objectives and `(1/3 - epsilon)` for non-monotone objectives under matroid constraints, using `O((n / epsilon) log(r / epsilon) * (k * EO + IO))` oracle complexity
- Key techniques: decreasing thresholds, matroid exchange construction between the greedy solution and a transformed optimum, and per-iteration charging arguments adapted from greedy proofs
- Status: processed-deep; venue-year-to-verify
- Tags: #k-submodular #matroid #threshold #query-efficient #non-monotone #monotone
- Inbox source: inbox/2307.13996v1.pdf