# Metadata

- Title: Size-Constrained k-Submodular Maximization in Near-Linear Time
- Authors: Guanyu Nie, Yanhui Zhu, Yididiya Y. Nadew, A. Pavan, Christopher John Quinn, Samik Basu
- Year: 2023
- Venue: Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence (UAI 2023), PMLR 216:1545-1554
- Primary group: k-submodular
- Secondary tags: monotone, total-size, individual-size, thresholding, near-linear, deterministic
- Problem: monotone k-submodular maximization under total size constraints and under individual size constraints, with emphasis on reducing oracle complexity
- Main guarantee: threshold-greedy algorithms achieve `(1/2 - epsilon)` under total size and `(1/3 - epsilon)` under individual size using `O(nk / epsilon * log(B / epsilon))` value-oracle calls, removing linear dependence on the budgets and improving over prior stochastic individual-size complexity by a factor of `k`
- Key techniques: decreasing threshold schedules from the best singleton value, exchange-style approximation proofs against aligned optimal solutions, type-swapping construction for individual budgets, lazy-evaluable threshold scans
- Status: processed-deep
- Tags: #k-submodular #size-constraints #total-size #individual-size #thresholding #deterministic
- Inbox source: inbox/nie23a.pdf; supplementary material in inbox/nie23a-supp.pdf