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 [Formula presented](1−[Formula presented])-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−[Formula presented]−ϵ. 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 [Formula presented](1−[Formula presented])-approximation.

Generalized budgeted submodular set function maximization

Monaco G.;
2021

Abstract

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 [Formula presented](1−[Formula presented])-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−[Formula presented]−ϵ. 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 [Formula presented](1−[Formula presented])-approximation.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11697/166466
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact