{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T09:59:45Z","timestamp":1769075985124,"version":"3.49.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T00:00:00Z","timestamp":1656892800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T00:00:00Z","timestamp":1656892800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Comput Intell Syst"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We address the Budgeted Maximum Coverage Problem (BMCP), which is a natural and more practical extension of the standard 0\u20131 knapsack problem and the set cover problem. Given <jats:italic>m<\/jats:italic> elements with nonnegative weights, <jats:italic>n<\/jats:italic> subsets of elements with nonnegative costs, and a total budget, BMCP aims to select some subsets such that the total cost of selected subsets does not exceed the budget, and the total weight of associated elements is maximized. In this paper, we propose a variable depth local search algorithm (VDLS) for the BMCP. VDLS first generates an initial solution by a greedy algorithm, then iteratively improves the solution through a partial depth-first search method, that can improve the solution by simultaneously changing the states (selected or not) of multiple subsets. Such method allows VDLS to explore the solution space widely and deeply, and to yield high-quality solutions. We further propose a neighbor structure to boost the algorithm performance, that is, both subsets have a neighbor relation if they share at least one common associated element. By applying the neighbor structure, VDLS can adjust the selected subsets while losing as few covered elements as possible. Since the existing BMCP benchmarks only have simple structures and small scales, we design 60 new instances with relatively large scales and complex structures to enrich the diversity of the BMCP instances. Experimental results on 30 public instances and 60 new instances we designed demonstrate that VDLS significantly outperforms the existing heuristic and the general CPLEX exact solver.<\/jats:p>","DOI":"10.1007\/s44196-022-00096-3","type":"journal-article","created":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T23:02:46Z","timestamp":1656975766000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Effective Variable Depth Local Search for the Budgeted Maximum Coverage Problem"],"prefix":"10.1007","volume":"15","author":[{"given":"Jianrong","family":"Zhou","sequence":"first","affiliation":[]},{"given":"Jiongzhi","family":"Zheng","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7627-4604","authenticated-orcid":false,"given":"Kun","family":"He","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,4]]},"reference":[{"issue":"1","key":"96_CR1","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":"96_CR2","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, Berlin (2004)"},{"issue":"6","key":"96_CR3","doi-asserted-by":"publisher","first-page":"1152","DOI":"10.1287\/opre.20.6.1152","volume":"20","author":"E Balas","year":"1972","unstructured":"Balas, E., Padberg, M.W.: On the set-covering problem. Oper. Res. 20(6), 1152\u20131161 (1972)","journal-title":"Oper. Res."},{"issue":"1","key":"96_CR4","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions - I. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"2","key":"96_CR5","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/261342.571216","volume":"28","author":"DS Hochba","year":"1997","unstructured":"Hochba, D.S.: Approximation algorithms for NP-hard problems. SIGACT News 28(2), 40\u201352 (1997)","journal-title":"SIGACT News"},{"issue":"10","key":"96_CR6","doi-asserted-by":"publisher","first-page":"1564","DOI":"10.1016\/j.comcom.2005.07.009","volume":"29","author":"K Suh","year":"2006","unstructured":"Suh, K., Guo, Y., Kurose, J.F., Towsley, D.F.: Locating network monitors: complexity, heuristics, and coverage. Comput. Commun. 29(10), 1564\u20131577 (2006)","journal-title":"Comput. Commun."},{"key":"96_CR7","doi-asserted-by":"crossref","unstructured":"Li, L., Wang, D., Li, T., Knox, D., Padmanabhan, B.: SCENE: a scalable two-stage personalized news recommendation system. In: Proceeding of SIGIR 2011, pp. 125\u2013134 (2011)","DOI":"10.1145\/2009916.2009937"},{"key":"96_CR8","doi-asserted-by":"publisher","first-page":"104203","DOI":"10.1016\/j.engappai.2021.104203","volume":"100","author":"C Jana","year":"2021","unstructured":"Jana, C., Pal, M.: A dynamical hybrid method to design decision making process based on GRA approach for multiple attributes problem. Eng. Appl. Artif. Intell. 100, 104203 (2021)","journal-title":"Eng. Appl. Artif. Intell."},{"key":"96_CR9","doi-asserted-by":"crossref","unstructured":"Jana, C., Pal, M.: Extended bipolar fuzzy EDAS approach for multi-criteria group decision-making process. Comput. Appl. Math. 40(1) (2021)","DOI":"10.1007\/s40314-020-01403-4"},{"issue":"3","key":"96_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s40314-022-01806-5","volume":"41","author":"C Jana","year":"2022","unstructured":"Jana, C., Pal, M., Liu, P.: Multiple attribute dynamic decision making method based on some complex aggregation functions in cqrof setting. Comput. Appl. Math. 41(3), 1\u201328 (2022)","journal-title":"Comput. Appl. Math."},{"issue":"3","key":"96_CR11","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1109\/TNSM.2016.2598549","volume":"13","author":"B Kar","year":"2016","unstructured":"Kar, B., Wu, E.H., Lin, Y.: The budgeted maximum coverage problem in partially deployed software defined networks. IEEE Trans. Netw. Serv. Manage. 13(3), 394\u2013406 (2016)","journal-title":"IEEE Trans. Netw. Serv. Manage."},{"issue":"1","key":"96_CR12","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":"96_CR13","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Kumar, A.: Maximum coverage problem with group budget constraints and applications. In: Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, vol. 3122, pp. 72\u201383 (2004)","DOI":"10.1007\/978-3-540-27821-4_7"},{"key":"96_CR14","doi-asserted-by":"crossref","unstructured":"Curtis, D.E., Pemmaraju, S.V., Polgreen, P.: Budgeted maximum coverage with overlapping costs: Monitoring the emerging infections network. In: Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments, ALENEX 2010, pp. 112\u2013123 (2010)","DOI":"10.1137\/1.9781611972900.11"},{"key":"96_CR15","unstructured":"van Heuven\u00a0van Staereling, I., de Keijzer, B., Sch\u00e4fer, G.: The ground-set-cost budgeted maximum coverage problem. In: 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, vol. 58, pp. 50\u201315013 (2016)"},{"issue":"6","key":"96_CR16","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1002\/1520-6750(199410)41:6<833::AID-NAV3220410611>3.0.CO;2-Q","volume":"41","author":"O Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Nehme, D., Yu, G.: Note: On the set-union knapsack problem. Nav. Res. Logist. 41(6), 833\u2013842 (1994)","journal-title":"Nav. Res. Logist."},{"key":"96_CR17","doi-asserted-by":"publisher","first-page":"115310","DOI":"10.1016\/j.eswa.2021.115310","volume":"183","author":"L Li","year":"2021","unstructured":"Li, L., Wei, Z., Hao, J.-K., He, K.: Probability learning based tabu search for the budgeted maximum coverage problem. Expert Syst. Appl. 183, 115310 (2021)","journal-title":"Expert Syst. Appl."},{"key":"96_CR18","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.dam.2013.12.015","volume":"169","author":"A Arulselvan","year":"2014","unstructured":"Arulselvan, A.: A note on the set union knapsack problem. Discret. Appl. Math. 169, 214\u2013218 (2014)","journal-title":"Discret. Appl. Math."},{"key":"96_CR19","unstructured":"Taylor, R.: Approximations of the densest k-subhypergraph and set union knapsack problems. CoRR abs\/1610.04935 (2016)"},{"key":"96_CR20","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.future.2017.05.044","volume":"78","author":"Y He","year":"2018","unstructured":"He, Y., Xie, H., Wong, T., Wang, X.: A novel binary artificial bee colony algorithm for the set-union knapsack problem. Futur. Gener. Comput. Syst. 78, 77\u201386 (2018)","journal-title":"Futur. Gener. Comput. Syst."},{"key":"96_CR21","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1016\/j.future.2019.07.062","volume":"101","author":"Z Wei","year":"2019","unstructured":"Wei, Z., Hao, J.: Iterated two-phase local search for the set-union knapsack problem. Futur. Gener. Comput. Syst. 101, 1005\u20131017 (2019)","journal-title":"Futur. Gener. Comput. Syst."},{"key":"96_CR22","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/j.eswa.2019.06.007","volume":"135","author":"G Lin","year":"2019","unstructured":"Lin, G., Guan, J., Li, Z., Feng, H.: A hybrid binary particle swarm optimization with tabu search for the set-union knapsack problem. Expert Syst. Appl. 135, 201\u2013211 (2019)","journal-title":"Expert Syst. Appl."},{"issue":"3","key":"96_CR23","doi-asserted-by":"publisher","first-page":"1883","DOI":"10.1007\/s00500-019-04021-3","volume":"24","author":"C Wu","year":"2020","unstructured":"Wu, C., He, Y.: Solving the set-union knapsack problem by a novel hybrid jaya algorithm. Soft. Comput. 24(3), 1883\u20131902 (2020)","journal-title":"Soft. Comput."},{"key":"96_CR24","doi-asserted-by":"publisher","first-page":"113802","DOI":"10.1016\/j.eswa.2020.113802","volume":"165","author":"Z Wei","year":"2021","unstructured":"Wei, Z., Hao, J.: Kernel based tabu search for the set-union knapsack problem. Expert Syst. Appl. 165, 113802 (2021)","journal-title":"Expert Syst. Appl."},{"key":"96_CR25","doi-asserted-by":"crossref","unstructured":"Piva, B.: Approximations for restrictions of the budgeted and generalized maximum coverage problems. In: Proceedings of the Tenth Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019, vol. 346, pp. 667\u2013676 (2019)","DOI":"10.1016\/j.entcs.2019.08.058"}],"container-title":["International Journal of Computational Intelligence Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44196-022-00096-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s44196-022-00096-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s44196-022-00096-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,4]],"date-time":"2022-07-04T23:06:27Z","timestamp":1656975987000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s44196-022-00096-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,4]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["96"],"URL":"https:\/\/doi.org\/10.1007\/s44196-022-00096-3","relation":{},"ISSN":["1875-6883"],"issn-type":[{"value":"1875-6883","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,4]]},"assertion":[{"value":"26 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 July 2022","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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"43"}}