{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T11:14:12Z","timestamp":1772882052564,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T00:00:00Z","timestamp":1655078400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T00:00:00Z","timestamp":1655078400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12171444"],"award-info":[{"award-number":["12171444"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871442"],"award-info":[{"award-number":["11871442"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2019MA052"],"award-info":[{"award-number":["ZR2019MA052"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s10898-022-01193-5","type":"journal-article","created":{"date-parts":[[2022,6,13]],"date-time":"2022-06-13T04:02:56Z","timestamp":1655092976000},"page":"15-38","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A fast and deterministic algorithm for Knapsack-constrained monotone DR-submodular maximization over an integer lattice"],"prefix":"10.1007","volume":"85","author":[{"given":"Suning","family":"Gong","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0895-7793","authenticated-orcid":false,"given":"Qingqin","family":"Nong","sequence":"additional","affiliation":[]},{"given":"Shuyu","family":"Bao","sequence":"additional","affiliation":[]},{"given":"Qizhi","family":"Fang","sequence":"additional","affiliation":[]},{"given":"Ding-Zhu","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,13]]},"reference":[{"key":"1193_CR1","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"AA Ageev","year":"2004","unstructured":"Ageev, A.A., Sviridenko, M.I.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8, 307\u2013328 (2004)","journal-title":"J. Comb. Optim."},{"key":"1193_CR2","doi-asserted-by":"crossref","unstructured":"Alon N., Gamzu I., Tennenholtz M.: Optimizing budget allocation among channels and influencers. Proceedings of the 21st international conference on World Wide Web, 381-388 (2012)","DOI":"10.1145\/2187836.2187888"},{"key":"1193_CR3","doi-asserted-by":"crossref","unstructured":"Anari N., Goel G., Nikzad A.: Mechanism design for crowdsourcing: An optimal $$1-1\/e$$ competitive budget-feasible mechanism for large markets. 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, 266-275 (2014)","DOI":"10.1109\/FOCS.2014.36"},{"key":"1193_CR4","doi-asserted-by":"crossref","unstructured":"Badanidiyuru A., Vondr\u00e1k J.: Fast algorithms for maximizing submodular functions. Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms, 1497-1514 (2014)","DOI":"10.1137\/1.9781611973402.110"},{"key":"1193_CR5","unstructured":"Bian A., Levy K., Krause A., Buhmann J.M.: Continuous dr-submodular maximization: Structure and algorithms. Advances in Neural Information Processing Systems, 486\u2013496 (2017)"},{"issue":"6","key":"1193_CR6","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."},{"key":"1193_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri C, Quanrud K.: Submodular function maximization in parallel via the multilinear relaxation. Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, 303-322 (2019)","DOI":"10.1137\/1.9781611975482.20"},{"key":"1193_CR8","doi-asserted-by":"crossref","unstructured":"Chekuri C., Vondr\u00e1k J., Zenklusen R.: Dependent randomized rounding via exchange properties of combinatorial structures. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 575-584 (2010)","DOI":"10.1109\/FOCS.2010.60"},{"key":"1193_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri C., Vondr\u00e1k J., Zenklusen R.: Multi-budgeted matchings and matroid intersection via dependent rounding. Proceedings of the 2011 Annual ACM-SIAM Symposium on Discrete Algorithms, 1080-1097 (2011)","DOI":"10.1137\/1.9781611973082.82"},{"issue":"6","key":"1193_CR10","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1137\/110839655","volume":"43","author":"C Chekuri","year":"2014","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6), 1831\u20131879 (2014)","journal-title":"SIAM J. Comput."},{"key":"1193_CR11","unstructured":"Ene A., Nguy$$\\tilde{\\check{\\rm e}}$$n H.L.: A nearly-linear time algorithm for submodular maximization with a knapsack constraint. 46th International Colloquium on Automata, Languages, and Programming, 53:1-53:12 (2019)"},{"key":"1193_CR12","unstructured":"Ene A, Nguy$$\\tilde{\\check{\\rm e}}$$n H L: A reduction for optimizing lattice submodular functions with diminishing returns, arXiv preprint arXiv:1606.08362, (2016)"},{"issue":"4","key":"1193_CR13","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"key":"1193_CR14","doi-asserted-by":"crossref","unstructured":"Feldman M., Naor J., Schwartz R.: A unified continuous greedy algorithm for submodular maximization. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 570-579 (2011)","DOI":"10.1109\/FOCS.2011.46"},{"key":"1193_CR15","doi-asserted-by":"crossref","unstructured":"Fisher M.L., Nemhauser G.L., Wolsey L.A.: An analysis of approximations for maximizing submodular set functions-II. Polyhedral Combinatorics, 73-87 (1978)","DOI":"10.1007\/BFb0121195"},{"key":"1193_CR16","volume-title":"Submodular functions and optimization, 58","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular functions and optimization, 58. Elsevier Science, Boston, Massachusetts (2005)"},{"issue":"1","key":"1193_CR17","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.ejor.2008.08.022","volume":"198","author":"B Goldengorin","year":"2009","unstructured":"Goldengorin, B.: Maximization of submodular functions: Theory and enumeration algorithms. Eur. J. Oper. Res. 198(1), 102\u2013112 (2009)","journal-title":"Eur. J. Oper. Res."},{"key":"1193_CR18","unstructured":"Goldengorin B., Tijssen G.A., Tso M.: The maximization of submodular functions: Old and new proofs for the correctness of the dichotomy algorithm, Graduate School\/Research Institute Systems, Organisation and Management (1999)"},{"key":"1193_CR19","doi-asserted-by":"crossref","unstructured":"Gottschalk C., Peis B.: Submodular function maximization over distributive and integer lattices, arXiv:1505.05423 (2015)","DOI":"10.1007\/978-3-319-28684-6_12"},{"key":"1193_CR20","unstructured":"Hassani H., Soltanolkotabi M., Karbasi A.: Gradient methods for submodular maximization. Advances in Neural Information Processing Systems, 5841-5851 (2017)"},{"key":"1193_CR21","doi-asserted-by":"crossref","unstructured":"Kapralov M., Post I., Vondr\u00e1k J.: Online submodular welfare maximization: Greedy is optimal. Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms, 1216-1225 (2013)","DOI":"10.1137\/1.9781611973105.88"},{"issue":"1","key":"1193_CR22","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.S.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39\u201345 (1999)","journal-title":"Inf. Process. Lett."},{"key":"1193_CR23","unstructured":"Krause A., Guestrin C.: Near-optimal nonmyopic value of information in graphical models. Proceedings of Uncertainty in Artificial Intelligence, 324-331 (2005)"},{"key":"1193_CR24","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., Singh, A.P., Guestrin, C.: Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235\u2013284 (2008)","journal-title":"J. Mach. Learn. Res."},{"issue":"4","key":"1193_CR25","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1287\/moor.2013.0592","volume":"38","author":"A Kulik","year":"2013","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Math. Oper. Res. 38(4), 729\u2013739 (2013)","journal-title":"Math. Oper. Res."},{"key":"1193_CR26","unstructured":"Lin H., Bilmes J.: A class of submodular functions for document summarization. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, 1, 510-520 (2011)"},{"key":"1193_CR27","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz L.: Submodular functions and convexity. Mathematical Programming The State of the Art, 235-257 (1983)","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"1193_CR28","doi-asserted-by":"crossref","unstructured":"Maehara T., Nakashima S., Yamaguchi Y.: Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice. Mathematical Programming, 1-35 (2021)","DOI":"10.1007\/s10107-021-01620-7"},{"key":"1193_CR29","unstructured":"Mokhtari A., Hassani H., Karbasi A.: Conditional gradient method for stochastic submodular maximization: closing the gap. International Conference on Artificial Intelligence and Statistics, 1886-1895 (2018)"},{"issue":"01","key":"1193_CR30","doi-asserted-by":"publisher","first-page":"4618","DOI":"10.1609\/aaai.v33i01.33014618","volume":"33","author":"S Nakashima","year":"2019","unstructured":"Nakashima, S., Maehara, T.: Subspace selection via DR-submodular maximization on lattices. Proceedings of the AAAI Conference on Artificial Intelligence 33(01), 4618\u20134625 (2019)","journal-title":"Proceedings of the AAAI Conference on Artificial Intelligence"},{"issue":"3","key":"1193_CR31","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177\u2013188 (1978)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1193_CR32","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."},{"key":"1193_CR33","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.dsm.2021.12.002","volume":"4","author":"R Pugliese","year":"2021","unstructured":"Pugliese, R., Regondi, S., Marini, R.: Machine learning-based approach: Global trends, research directions, and regulatory standpoints. Data Science and Management 4, 19\u201329 (2021)","journal-title":"Data Science and Management"},{"key":"1193_CR34","doi-asserted-by":"crossref","unstructured":"Singer Y.: How to win friends and influence people, truthfully: influence maximization mechanisms for social networks. Proceedings of the fifth ACM international conference on Web search and data mining, 733-742 (2012)","DOI":"10.1145\/2124295.2124381"},{"key":"1193_CR35","unstructured":"Soma T., Kakimura N., Inaba K., Kawarabayashi K.: Optimal budget allocation: Theoreticalguarantee and efficient algorithm. International Conference on Machine Learning, 351-359 (2014)"},{"key":"1193_CR36","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s10107-018-1324-y","volume":"172","author":"T Soma","year":"2018","unstructured":"Soma, T., Yoshida, Y.: Maximizing monotone submodular functions over the integer lattice. Math. Program. 172, 539\u2013563 (2018)","journal-title":"Math. Program."},{"issue":"1","key":"1193_CR37","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"3","key":"1193_CR38","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"LA Wolsey","year":"1982","unstructured":"Wolsey, L.A.: Maximising real-valued submodular functions: Primal and dual heuristics for location problems. Math. Oper. Res. 7(3), 410\u2013425 (1982)","journal-title":"Math. Oper. Res."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-022-01193-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-022-01193-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-022-01193-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,7]],"date-time":"2023-01-07T08:06:51Z","timestamp":1673078811000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-022-01193-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,13]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["1193"],"URL":"https:\/\/doi.org\/10.1007\/s10898-022-01193-5","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,13]]},"assertion":[{"value":"22 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}