Cellinese, Francesco ;
D'Angelo, Gianlorenzo ;
Monaco, Gianpiero ;
Velaj, Yllka
Generalized Budgeted Submodular Set Function Maximization
Abstract
In this paper we consider a generalization of the wellknown 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(11/e^alpha), where alpha <= 1 is the approximation factor of an algorithm for a subproblem. We give two polynomialtime algorithms to solve this subproblem. 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=11/eepsilon for the general case. The gap between our approximation guarantees and the known inapproximability bounds is 1/2.
We extend our algorithm to a bicriterion approximation algorithm in which we are allowed to spend an extra budget up to a factor beta >= 1 to guarantee a 1/2(11/e^(alpha beta))approximation. If we set beta=1/(alpha)ln (1/(2 epsilon)), the algorithm achieves an approximation factor of 1/2epsilon, for any arbitrarily small epsilon>0.
BibTeX  Entry
@InProceedings{cellinese_et_al:LIPIcs:2018:9613,
author = {Francesco Cellinese and Gianlorenzo D'Angelo and Gianpiero Monaco and Yllka Velaj},
title = {{Generalized Budgeted Submodular Set Function Maximization}},
booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
pages = {31:131:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770866},
ISSN = {18688969},
year = {2018},
volume = {117},
editor = {Igor Potapov and Paul Spirakis and James Worrell},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9613},
URN = {urn:nbn:de:0030drops96138},
doi = {10.4230/LIPIcs.MFCS.2018.31},
annote = {Keywords: Submodular set function, Approximation algorithms, Budgeted Maximum Coverage}
}
2018
Keywords: 

Submodular set function, Approximation algorithms, Budgeted Maximum Coverage 
Seminar: 

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Issue date: 

2018 
Date of publication: 

2018 