Generalized budgeted submodular set function maximization

In the generalized budgeted submodular set function maximization problem, we are given a ground set of elements and a set of bins. Each bin has its own cost and the cost of each element depends on its associated bin. The goal is to find a subset of elements along with an associated set of bins such that the overall costs of both is at most a given budget, and the profit is maximized. We present an algorithm that guarantees a 1 2 ( 1 − 1 e α ) -approximation, where α ≤ 1 is the approximation factor of an algorithm for a sub-problem. If the costs satisfy a specific condition, we provide a polynomial-time algorithm that gives us α = 1 − ϵ, while for the general case we design an algorithm with α = 1 − 1 e − ϵ. We extend our results providing a bi-criterion approximation algorithm where we can spend an extra budget up to a factor β ≥ 1 to guarantee a 1 2 ( 1 − 1 e α β ) -approximation.

Authors

• Francesco Cellinese
• Gianlorenzo D'Angelo Gran Sasso Science Institute
• Gianpiero Monaco
• Yllka Velaj

Keywords

• Submodular set function
• Approximation algorithms
• Budgeted maximum coverage