Geometry-Dependent Approximation for Non-Monotone $k$-Submodular Maximization

作者：Vaneet Aggarwal · 单位：Purdue University, We study nonnegative, non-monotone k-submodular maximization with k ≥2 labels under support, A k-submodular objective f evaluates labelings in which each selected element receives one of, k ≥2 labels and the remaining elements stay unselected (Huber and Kolmogorov, 2012, and Živný, 2016). This selection-and-labeling structure appears in multi-type sensor placement and, the multi-class cut: for nonnegative pair weights wuv and label classes S1, . . . , Sk, It rewards separating interacting elements across label classes, while assigning an entire tightly, connected group to one label can decrease the value. Section 2.1 verifies nonnegativity and k-, submodularity and shows that this objective can be combined with monotone labeled coverage, We study this broader class under constraints that depend on the support but not on its labels, its assigned label. Upper quotas on selected locations or users in disjoint groups give a partition ma-, separate inventories or quotas for individual labels. · 会议/期刊：arXiv preprint · 方向：cs.DS · 发布日期：2026-10-06