Abstract
We study the following natural variant of the budgeted maximum coverage problem: We are given a budget B and a hypergraph G = (V, E), where each vertex has a nonnegative cost and a nonnegative profit. The goal is to select a set of hyperedges T subseteq E such that the total cost of the vertices covered by T is at most B and the total profit of all covered vertices is maximized. Besides being a natural generalization of the wellstudied maximum coverage problem, our motivation for investigating this problem originates from its application in the context of bid optimization in sponsored search auctions, such as Google AdWords.
It is easily seen that this problem is strictly harder than budgeted max coverage, which means that the problem is (11/e)inapproximable. The difference of our problem to the budgeted maximum coverage problem is that the costs are associated with the covered vertices instead of the selected hyperedges. As it turns out, this difference refutes the applicability of standard greedy approaches which are used to obtain constant factor approximation algorithms for several other variants of the maximum coverage problem. Our main results are as follows:
 We obtain a (1  1/sqrt(e))/2approximation algorithm for graphs.
 We derive a fully polynomialtime approximation scheme (FPTAS) if the incidence graph of the hypergraph is a forest (i.e., the hypergraph is Bergeacyclic). We also extend this result to incidence graphs with a fixedsize feedback hyperedge node set.
 We give a (1epsilon)/(2d^2)approximation algorithm for every epsilon > 0, where d is the maximum degree of a vertex in the hypergraph.
BibTeX  Entry
@InProceedings{vanheuvenvanstaereling_et_al:LIPIcs:2016:6502,
author = {Irving van Heuven van Staereling and Bart de Keijzer and Guido Sch{\"a}fer},
title = {{The GroundSetCost Budgeted Maximum Coverage Problem}},
booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
pages = {50:150:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770163},
ISSN = {18688969},
year = {2016},
volume = {58},
editor = {Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6502},
URN = {urn:nbn:de:0030drops65020},
doi = {10.4230/LIPIcs.MFCS.2016.50},
annote = {Keywords: maximum coverage problem, approximation algorithms, hypergraphs, submodular optimization, sponsored search}
}
Keywords: 

maximum coverage problem, approximation algorithms, hypergraphs, submodular optimization, sponsored search 
Collection: 

41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) 
Issue Date: 

2016 
Date of publication: 

19.08.2016 