2018/08/09 by Cellinese, Francesco, D'Angelo, Gianlorenzo, Monaco, Gianpiero +1
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1808.03085
In this paper we consider a generalization of the well-known budgeted maximum coverage problem. We are given a ground set of elements and a set of bins. The goal is to find a subset of elements along with an associated set of bins, such that the overall cost is at most a given budget, and the profit is maximized. Each bin has its own cost and the cost of each element depends on its associated bin. The profit is measured by a monotone submodular function over the elements. We first present an algorithm that guarantees an approximation factor of (1)/(2)(1-(1)/(eα)), where α≤ 1 is the approximation factor of an algorithm for a sub-problem. We give two polynomial-time algorithms to solve this sub-problem. The first one gives us α=1- ε if the costs satisfies a specific condition, which is fulfilled in several relevant cases, including the unitary costs case and the problem of maximizing a monotone submodular function under a knapsack constraint. The second one guarantees α=1-(1)/(e)-ε for the general case. The gap between our approximation guarantees and the known inapproximability bounds is (1)/(2). We extend our algorithm to a bi-criterion approximation algorithm in which we are allowed to spend an extra budget up to a factor β≥ 1 to guarantee a (1)/(2)(1-\frac1eαβ)-approximation. If we set β=\frac1αln ((1)/(2ε)), the algorithm achieves an approximation factor of (1)/(2)-ε, for any arbitrarily small ε>0.