The ground-set-cost budgeted maximum coverage problem

Irving Van Heuven Van Staereling*, Bart De Keijzer, Guido Schäfer

*Corresponding author for this work

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 non-negative cost and a non-negative profit. The goal is to select a set of hyperedges T c 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 well-studied 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 (1 - 1/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/ p e)/2-approximation algorithm for graphs. We derive a fully polynomial-time approximation scheme (FPTAS) if the incidence graph of the hypergraph is a forest (i.e., the hypergraph is Berge-acyclic). We also extend this result to incidence graphs with a fixed-size feedback hyperedge node set. We give a (1 - ϵ)/(2d2)-approximation algorithm for every ϵ > 0, where d is the maximum degree of a vertex in the hypergraph.

Original languageEnglish
Title of host publication41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
EditorsAnca Muscholl, Piotr Faliszewski, Rolf Niedermeier
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770163
DOIs
Publication statusPublished - 1 Aug 2016
Event41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016 - Krakow, Poland
Duration: 22 Aug 201626 Aug 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume58
ISSN (Print)1868-8969

Conference

Conference41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016
CountryPoland
CityKrakow
Period22/08/1626/08/16

Keywords

  • Approximation algorithms
  • Hypergraphs
  • Maximum coverage problem
  • Sponsored search
  • Submodular optimization

Fingerprint

Dive into the research topics of 'The ground-set-cost budgeted maximum coverage problem'. Together they form a unique fingerprint.

Cite this