2026-07-21T14:08:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9613 2024-03-06T10:44:32Z ddc:004 open_access

Generalized Budgeted Submodular Set Function Maximization Cellinese, Francesco D'Angelo, Gianlorenzo Monaco, Gianpiero Velaj, Yllka Submodular set function Approximation algorithms Budgeted Maximum Coverage 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^alpha), where alpha <= 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 alpha=1- epsilon 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 alpha=1-1/e-epsilon 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 beta >= 1 to guarantee a 1/2(1-1/e^(alpha beta))-approximation. If we set beta=1/(alpha)ln (1/(2 epsilon)), the algorithm achieves an approximation factor of 1/2-epsilon, for any arbitrarily small epsilon>0. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Francesco Cellinese and Gianlorenzo D'Angelo and Gianpiero Monaco and Yllka Velaj 2018 Is Part Of LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2018.31 urn:nbn:de:0030-drops-96138 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.31 eng https://creativecommons.org/licenses/by/3.0/legalcode