Approximation Algorithms for Monotone k-Submodular Maximization Under the Chance Constraint
摘要
Submodular optimization is an important topic in the field of combinatorial optimization. The k-submodular function is a generalization of the submodular function. Many machine learning problems, such as placing k types of sensors, can be formulated as maximizing a monotone k-submodular function. In real-world optimization problems where the constraints involve random components, chance constraints are often used to limit the probability of constraint violations due to random factors. In this paper, we investigate the problem of maximizing a monotone k-submodular function under the chance constraint. Specifically, each element e is assigned a random weight independently sampled from a uniform distribution. We study two distinct cases, in which the weights are drawn from a common uniform distribution or from element-specific uniform distributions, all with the same dispersion. For the first case, this paper designs a threshold-decreasing algorithm with an approximation ratio of \(1/2-\epsilon \) . For the second case, this paper first designs a deterministic algorithm, which uses the method of dividing the ground set into two parts, and then combines its output solution with the threshold-greedy algorithm to design an algorithm with an approximation ratio of \(1/3-\epsilon \) .