The Multi-budget Maximum Weighted Coverage Problem

Francesco Cellinese, Gianlorenzo D'Angelo, Gianpiero Monaco, Yllka Velaj

Veröffentlichungen: Beitrag in BuchBeitrag in KonferenzbandPeer Reviewed

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.
OriginalspracheEnglisch
TitelAlgorithms and Complexity
Herausgeber (Verlag)Springer
Seiten173-186
Seitenumfang14
Band12701
ISBN (Print)978-3-030-75241-5
DOIs
PublikationsstatusVeröffentlicht - 1 Mai 2021

Publikationsreihe

ReiheLecture Notes in Computer Science
ISSN0302-9743

ÖFOS 2012

  • 102033 Data Mining

Zitationsweisen