Monotone k-Submodular Function Maximization with Size Constraints
A k-submodular function is a generalization of a submodular function, where the input consists of k disjoint subsets, instead of a single subset, of the domain. Many machine learning problems, including influence maximization with k kinds of topics and sensor placement with k kinds of sensors, can be naturally modeled as the problem of maximizing monotone k-submodular functions. In this paper, we give constant-factor approximation algorithms for maximizing monotone ksubmodular functions subject to several size constraints. The running time of our algorithms are almost linear in the domain size. We experimentally demonstrate that our algorithms outperform baseline algorithms in terms of the solution quality.
This paper studies the problem of maximizing monotone k-submodular maximization under either a total size constraint or a set of individual size constraints. For both classes of constraints it proposes two variants of greedy algorithms: k-greedy and k-stochastic greedy. For the total size constraint case, both algorithms, in general, provide a guarantee of 1/2. And a guarantee of 1/3 is given for the individual size constraint case. In the experiments, the proposed algorithms are observed to give better function valuation than baseline methods. This paper study the extension of submodularity to k-submodularity and generalizes the classical greedy algorithm to this setting. However, I think it would very interesting to see more applications of k-submodularity besides sensor placement and influence maximization. The stochastic variant of the greedy algorithm is very similar to the following paper:Lazier Than Lazy Greedy, Mirzasoleiman et al AAAI 2015.Instead of showing that the stochastic greedy gives a solution with bound 1/2 with probability 1-\delta, I think the authors can also give an expectation bound: the stochastic greedy algorithm always gives a solution on expectation with bound 1/2 - \delta. In the experiments, it seems that the performance of the stochastic greedy sometimes works even better than the greedy algorithm (as shown in Fig 1 and 3), which is different from the results as reported in the lazier than lazy greedy paper. I am hoping the authors could further investigate why and give some comments on this observation.   Minor comments:For the proposed algorithms, it seems that the authors actually have used the lazy evaluation trick (minoux' trick) in the experiments, but I think it would be better to describe and discuss how to use the lazy evaluation trick when describing the algorithms.line 60-62: One may not use the computationally expensive algorithm that is tight with bound (1-1/e) for solving submodular maximization under the partition matroid constraint. Instead, a simple greedy algorithm very much the same as the one proposed in this work can solve it with guarantee 1/2.  For the sensor placement experiment, it seems that the objective is defined as the entropy function. But it is unclear how the entropy function is evaluated, since this function requires exponential complexity to evaluate. Please describe in more detail.