# zbMATH — the first resource for mathematics

The budgeted maximum coverage problem. (English) Zbl 1002.68203
Summary: The budgeted maximum coverage problem is: given a collection $$S$$ of sets with associated costs defined over a domain of weighted elements, and a budget $$L$$, find a subset $$S'$$ of $$S$$ such that the total cost of the sets in $$S'$$ does not exceed $$L$$, and the total weight of the elements covered by $$S'$$ is maximized. This problem is NP-hard. For the special case of this problem where each set has unit cost, a $$(1-1/e)$$-approximation is known. Yet, prior to this work, no approximation results were known for the general cost version. The contribution of this paper is a $$(1-1/e)$$-approximation algorithm for the budgeted maximum coverage problem. We also argue that this approximation factor is the best possible, unless $$\text{NP}\subseteq\text{DTIME}(n^{O(\log\log n)})$$.

##### MSC:
 68W25 Approximation algorithms 68W40 Analysis of algorithms 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
##### Keywords:
budgeted maximum coverage problem
Full Text:
{"ft_lang_label":"__label__en","ft_lang_prob":0.893296,"math_prob":0.99753696,"size":1340,"snap":"2021-31-2021-39","text_gpt3_token_len":367,"char_repetition_ratio":0.125,"word_repetition_ratio":0.020512821,"special_character_ratio":0.28955224,"punctuation_ratio":0.17602997,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9996631,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-09-28T20:11:01Z\",\"WARC-Record-ID\":\"<urn:uuid:b6fd0ca1-eeeb-429d-be85-ba4411240ca1>\",\"Content-Length\":\"47509\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:38ee8b9a-8b5d-424a-ab93-0839b48968c2>\",\"WARC-Concurrent-To\":\"<urn:uuid:776dc6b4-51f2-438b-b78e-5702a0f437ac>\",\"WARC-IP-Address\":\"141.66.194.2\",\"WARC-Target-URI\":\"https://zbmath.org/?q=an:1002.68203\",\"WARC-Payload-Digest\":\"sha1:FUJX6WCVGONAUJTBN5D75BK2RDVPTIAO\",\"WARC-Block-Digest\":\"sha1:M2QIKCC2TIXBJBUTVIFRSXXJT2DUUOOG\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-39/CC-MAIN-2021-39_segments_1631780060882.17_warc_CC-MAIN-20210928184203-20210928214203-00049.warc.gz\"}"}