# Metadata

- Title: On Optimal Approximations for k-Submodular Maximization via Multilinear Extension
- Authors: Lingxiao Huang, Baoxiang Wang, Huanjian Zhou
- Year: 2021
- Venue: arXiv preprint (`arXiv:2107.07103v3`, September 5, 2023)
- Primary group: k-submodular
- Secondary tags: multilinear-extension, continuous-greedy, Frank-Wolfe, matroid, knapsack, non-monotone, rounding
- Problem: constrained k-submodular maximization under single matroid, `O(1)` knapsack constraints, and their intersections, for both monotone and non-monotone objectives
- Main guarantee: introduces a multilinear extension for k-submodular functions and obtains `1 / 2 - eps` for monotone single matroid or `O(1)` knapsacks, `1 / 3 - eps` for the non-monotone counterparts, and `0.3 / b - eps` or `0.2 / b - eps` for intersections with `b` matroids
- Key techniques: k-submodular multilinear extension on `Delta_k^n`, Frank-Wolfe-type continuous optimization, approximate linearity, pairwise monotonicity, auxiliary-point analysis, and rounding from conjunction relaxations
- Status: processed-deep, venue-year-to-verify
- Tags: #k-submodular #multilinear-extension #continuous-greedy #Frank-Wolfe #matroid #knapsack #approximation #arXiv
- Inbox source: inbox/2107.07103v3.pdf