In this paper we consider the multi-budget maximum weighted coverage problem, a generalization of the classical maximum coverage problem, where we are given k budgets, a set X of elements, and a set S of bins where any S∈ S is a subset of elements of X. Each bin S has its own cost, and each element its own weight. An outcome is a vector O= (O1, ⋯, Ok) where each budget bi, for i= 1, ⋯, k, can be used to buy a subset of bins Oi⊆ S of overall cost at most bi. The objective is to maximize the total weight which is defined as the sum of the weights of the elements bought with the budgets. We consider the classical combinatorial optimization problem of computing an outcome which maximizes the total weight and provide a (1-1e) -approximation algorithm for the case when the maximum cost of a bin is upper-bounded by the minimum budget, i.e. the case in which each budget can be used to buy any bin. Moreover, we give a randomized Monte-Carlo algorithm for the general case that runs in polynomial time, satisfies the budget constraints in expectation, and guarantees an expected 1-1e approximation factor.

### The Multi-budget Maximum Weighted Coverage Problem

#### Abstract

In this paper we consider the multi-budget maximum weighted coverage problem, a generalization of the classical maximum coverage problem, where we are given k budgets, a set X of elements, and a set S of bins where any S∈ S is a subset of elements of X. Each bin S has its own cost, and each element its own weight. An outcome is a vector O= (O1, ⋯, Ok) where each budget bi, for i= 1, ⋯, k, can be used to buy a subset of bins Oi⊆ S of overall cost at most bi. The objective is to maximize the total weight which is defined as the sum of the weights of the elements bought with the budgets. We consider the classical combinatorial optimization problem of computing an outcome which maximizes the total weight and provide a (1-1e) -approximation algorithm for the case when the maximum cost of a bin is upper-bounded by the minimum budget, i.e. the case in which each budget can be used to buy any bin. Moreover, we give a randomized Monte-Carlo algorithm for the general case that runs in polynomial time, satisfies the budget constraints in expectation, and guarantees an expected 1-1e approximation factor.
##### Scheda breve Scheda completa Scheda completa (DC)
2021
978-3-030-75241-5
978-3-030-75242-2
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### Pubblicazioni consigliate

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: `https://hdl.handle.net/11697/171813`
• ND
• 1
• ND