Maximization of Monotone k-Submodular Functions with Bounded Curvature and Non-k-Submodular Functions

Tatsuya Matsuoka (NEC Corporation)*; Naoto Ohsaka (NEC Corporation)


The concept of k-submodularity is an extension of submodularity, of which maximization has various applications, such as influence maximization and sensor placement. In such situations, to model complicated real problems, we want to deal with multiple factors, such as, more detailed parameter representing a property of a given function or a constraint which should be imposed for a given function, simultaneously. Besides, it is preferable that an algorithm for the modeling problem is simple. In this paper, for both monotone k-submodular function maximization with bounded curvature and monotone weakly k-submodular function maximization, we give approximation ratio analysis on greedy-type algorithms on the problem with the matroid constraint and that with the individual size constraint. Furthermore, we give an approximation ratio analysis on another type of the relaxation of k-submodular functions, approximately k-submodular functions, with the matroid constraint.