{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,25]],"date-time":"2026-01-25T02:27:05Z","timestamp":1769308025611,"version":"3.49.0"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T00:00:00Z","timestamp":1763596800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T00:00:00Z","timestamp":1763596800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/X021696\/1"],"award-info":[{"award-number":["EP\/X021696\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We study the following natural variant of the budgeted maximum coverage problem: We are given a budget\n                    <jats:italic>B<\/jats:italic>\n                    and a hypergraph\n                    <jats:inline-formula>\n                      <jats:tex-math>$$G = (V, E)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , where each vertex has a non-negative cost and a non-negative profit. The goal is to select a set of hyperedges\n                    <jats:inline-formula>\n                      <jats:tex-math>$$T \\subseteq E$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    such that the total cost of the vertices covered by\n                    <jats:italic>T<\/jats:italic>\n                    is at most\n                    <jats:italic>B<\/jats:italic>\n                    and the total profit of all covered vertices is maximized. This is a natural generalization of the maximum coverage problem. Our interest in this problem stems from its application to bid optimization in sponsored search auctions. It is easily seen that this problem is at least as hard as budgeted maximum coverage (where the costs are associated with the selected hyperedges instead of the covered vertices). This implies\n                    <jats:inline-formula>\n                      <jats:tex-math>$$(1-1\/e+\\epsilon )$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -inapproximability for any\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\epsilon&gt; 0$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . Furthermore, standard greedy approaches do not yield constant factor approximations for our variant of the problem. In fact, through a reduction from Densest\n                    <jats:italic>k<\/jats:italic>\n                    -Subgraph, it can be established that our problem is inapproximable up to a constant factor, conditional on the exponential time hypothesis. Our main results are as follows: (i.) We obtain a\n                    <jats:inline-formula>\n                      <jats:tex-math>$$(1 - 1\/\\sqrt{e})\/2$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -approximation algorithm for graphs. (ii.) We derive a fully polynomial-time approximation scheme (FPTAS) if the incidence graph of the hypergraph is a forest (i.e., the hypergraph is\n                    <jats:italic>Berge-acyclic<\/jats:italic>\n                    ). We extend this result to incidence graphs with a fixed-size feedback hyperedge node set. (iii.) We give a\n                    <jats:inline-formula>\n                      <jats:tex-math>$$(1-\\varepsilon )\/(2d^2)$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -approximation algorithm for all\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\varepsilon&gt; 0$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , where\n                    <jats:italic>d<\/jats:italic>\n                    is the maximum vertex degree.\n                  <\/jats:p>","DOI":"10.1007\/s00224-025-10248-5","type":"journal-article","created":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T02:21:58Z","timestamp":1763605318000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The Ground-Set-Cost Budgeted Maximum Coverage Problem"],"prefix":"10.1007","volume":"69","author":[{"given":"Irving","family":"van Heuven van Staereling","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9465-0837","authenticated-orcid":false,"given":"Bart","family":"de Keijzer","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1923-4902","authenticated-orcid":false,"given":"Guido","family":"Sch\u00e4fer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,11,20]]},"reference":[{"key":"10248_CR1","volume-title":"Approximation Algorithms for NP-hard Problems","author":"DS Hochbaum","year":"1997","unstructured":"Hochbaum, D.S.: Approximation Algorithms for NP-hard Problems. PWS Publishing Co., Worcester (1997)"},{"issue":"4","key":"10248_CR2","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"10248_CR3","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39\u201345 (1999)","journal-title":"Inf. Process. Lett."},{"key":"10248_CR4","doi-asserted-by":"crossref","unstructured":"Archak, N., Mirrokni, V., Muthukrishnan, S.: Budget optimization for online campaigns with positive carryover effects. In: Proceedings of the 8th International Conference on Internet and Network Economics, pp. 86\u201399. Springer (2012)","DOI":"10.1007\/978-3-642-35311-6_7"},{"key":"10248_CR5","doi-asserted-by":"crossref","unstructured":"Feldman, J., Muthukrishnan, S., P\u00e1l, M., Stein, C.: Budget optimization in search-based advertising auctions. In: Proceedings of the 8th ACM Conference on Electronic Commerce, pp. 40\u201349. Association for Computing Machinery (2007)","DOI":"10.1145\/1250910.1250917"},{"issue":"3","key":"10248_CR6","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s10660-012-9094-8","volume":"12","author":"P Maill\u00e9","year":"2012","unstructured":"Maill\u00e9, P., Markakis, E., Naldi, M., Stamoulis, G.D., Tuffin, B.: Sponsored search auctions: an overview of research with emphasis on game theoretic aspects. Electron. Commer. Res. 12(3), 265\u2013300 (2012)","journal-title":"Electron. Commer. Res."},{"key":"10248_CR7","doi-asserted-by":"crossref","unstructured":"Zhou, Y., Naroditskiy, V.: Algorithm for stochastic multiple-choice knapsack problem and application to keywords bidding. In: Proceedings of the 17th International Conference on World Wide Web, pp. 1175\u20131176. Association for Computing Machinery (2008)","DOI":"10.1145\/1367497.1367713"},{"issue":"6","key":"10248_CR8","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10248_CR9","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.ipl.2008.03.017","volume":"108","author":"R Cohen","year":"2008","unstructured":"Cohen, R., Katzir, L.: The generalized maximum coverage problem. Inf. Process. Lett. 108(1), 15\u201322 (2008)","journal-title":"Inf. Process. Lett."},{"key":"10248_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004)"},{"issue":"6","key":"10248_CR11","doi-asserted-by":"publisher","first-page":"1715","DOI":"10.1137\/100783352","volume":"40","author":"Z Svitkina","year":"2011","unstructured":"Svitkina, Z., Fleischer, L.: Submodular approximation: sampling-based algorithms and lower bounds. SIAM J. Comput. 40(6), 1715\u20131737 (2011)","journal-title":"SIAM J. Comput."},{"key":"10248_CR12","unstructured":"Iyer, R.K., Bilmes, J.A.: Submodular optimization with submodular cover and submodular knapsack constraints. In: Advances in Neural Information Processing Systems, pp. 2436\u20132444. MIT Press (2013)"},{"issue":"10","key":"10248_CR13","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1016\/j.ipl.2014.05.001","volume":"114","author":"T Kociumaka","year":"2014","unstructured":"Kociumaka, T., Pilipczuk, M.: Faster deterministic feedback vertex set. Inf. Process. Lett. 114(10), 556\u2013560 (2014)","journal-title":"Inf. Process. Lett."},{"key":"10248_CR14","doi-asserted-by":"crossref","unstructured":"Li, J., Nederlof, J.: Detecting feedback vertex sets of size $$k$$ in $$O^{*}(2.7^{k})$$ time. ACM Transactions on Algorithms 18(4), 1\u201326 (2022)","DOI":"10.1145\/3504027"},{"key":"10248_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2003","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2003)"},{"key":"10248_CR16","doi-asserted-by":"crossref","unstructured":"Manurangsi, P.: Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 954\u2013961. Association for Computing Machinery (2017)","DOI":"10.1145\/3055399.3055412"},{"key":"10248_CR17","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamtac, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: An $$O\\left(\\mathrm n^\\frac14\\right)$$ approximation for densest $$k$$-subgraph. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, pp. 201\u2013210. Association for Computing Machinery (2010)","DOI":"10.1145\/1806689.1806719"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10248-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10248-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10248-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T08:52:49Z","timestamp":1769244769000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10248-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,20]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10248"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10248-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,20]]},"assertion":[{"value":"28 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"39"}}