Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Cellinese, Francesco; D'Angelo, Gianlorenzo; Monaco, Gianpiero; Velaj, Yllka http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-96138
URL:

; ; ;

Generalized Budgeted Submodular Set Function Maximization

pdf-format:


Abstract

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.

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:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9613},
  URN =		{urn:nbn:de:0030-drops-96138},
  doi =		{10.4230/LIPIcs.MFCS.2018.31},
  annote =	{Keywords: Submodular set function, Approximation algorithms, Budgeted Maximum Coverage}
}

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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI