k -Submodular maximization with two kinds of constraints Academic Article uri icon

abstract

  • [Formula: see text]-submodular maximization is a generalization of submodular maximization, which requires us to select [Formula: see text] disjoint subsets instead of one subset. Attracted by practical values and applications, we consider [Formula: see text]-submodular maximization with two kinds of constraints. For total size and individual size difference constraints, we present a [Formula: see text]-approximation algorithm for maximizing a nonnegative k-submodular function, running in time [Formula: see text] at worst. Specially, if [Formula: see text] is multiple of [Formula: see text], the approximation ratio can reduce to [Formula: see text], running in time [Formula: see text] at worst. Besides, this algorithm can be applied to [Formula: see text]-bisubmodular achieving [Formula: see text]-approximation running in time [Formula: see text]. Furthermore, if [Formula: see text] is multiple of 2, the approximation ratio can reduce to [Formula: see text], running in time [Formula: see text] at worst. For individual size constraint, there is a [Formula: see text]-approximation algorithm for maximizing a nonnegative [Formula: see text]-submodular function and an nonnegative [Formula: see text]-bisubmodular function, running in time [Formula: see text] and [Formula: see text] respectively, at worst.

author list (cited authors)

  • Shi, G., Gu, S., & Wu, W.

publication date

  • January 1, 2020 11:11 AM