{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T12:00:35Z","timestamp":1781092835419,"version":"3.54.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,7,17]],"date-time":"2020-07-17T00:00:00Z","timestamp":1594944000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,17]],"date-time":"2020-07-17T00:00:00Z","timestamp":1594944000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11531014"],"award-info":[{"award-number":["11531014"]}],"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":["11871081"],"award-info":[{"award-number":["11871081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"the Science and Technology Program of Beijing Education Commission","award":["KM201810005006"],"award-info":[{"award-number":["KM201810005006"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11971447"],"award-info":[{"award-number":["11971447"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"the Fundamental Research Funds for the Central Universities","award":["201964006"],"award-info":[{"award-number":["201964006"]}]},{"name":"the Natural Science Foundation of Shandong Province of China","award":["ZR2017QA010"],"award-info":[{"award-number":["ZR2017QA010"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s10878-020-00620-1","type":"journal-article","created":{"date-parts":[[2020,7,17]],"date-time":"2020-07-17T16:50:50Z","timestamp":1595004650000},"page":"1125-1148","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Maximizing a monotone non-submodular function under a knapsack constraint"],"prefix":"10.1007","volume":"43","author":[{"given":"Zhenning","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bin","family":"Liu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yishui","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dongmei","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,7,17]]},"reference":[{"key":"620_CR1","unstructured":"Balkanski E, Singer Y (2018) Approximation guarantees for adaptive sampling. In: Proceedings of ICML, pp 384\u2013393"},{"key":"620_CR2","unstructured":"Bian AA, Buhmann JM, Krause A, Tschiatschek S (2017b) Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of ICML, pp 498\u2013507"},{"key":"620_CR3","unstructured":"Bian A, Levy K, Krause A, Buhmann JM (2017a) Non-monotone continuous DR-submodular maximization: structure and algorithms. In: Proceedings of NIPS, pp 486\u2013496"},{"key":"620_CR4","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 (2011) Maximizing a submodular set function subject to a matroid constraint. SIAM J Comput 40:1740\u20131766","journal-title":"SIAM J Comput"},{"key":"620_CR5","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1214\/ss\/1177009939","volume":"10","author":"K Chaloner","year":"1995","unstructured":"Chaloner K, Verdinelli I (1995) Bayesian experimental design: a review. Stat Sci 10:273\u2013304","journal-title":"Stat Sci"},{"key":"620_CR6","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"M Conforti","year":"1984","unstructured":"Conforti M, Cornu\u00e9jols G (1984) Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado\u2013Edmonds theorem. Discrete Appl Math 7:251\u2013274","journal-title":"Discrete Appl Math"},{"key":"620_CR7","unstructured":"Iyer R, Bilmes J (2013) Submodular optimization with submodular cover and submodular knapsack constraints. In: Proceedings of NIPS, pp 2436\u20132444"},{"key":"620_CR8","unstructured":"Iyer R, Jegelka S, Bilmes J (2013) Curvature and optimal algorithms for learning and minimizing submodular functions. In: Proceedings of ICML, pp 2742\u20132750"},{"key":"620_CR9","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause A, Singh A, Guestrin C (2008) Nearoptimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies. J Mach Learn Res 9:235\u2013284","journal-title":"J Mach Learn Res"},{"key":"620_CR10","unstructured":"Kuhnle A, Smith JD, Crawford VG, Thai MT (2018) Fast maximization of non-submodular, monotonic functions on the integer lattice. In: Proceedings of ICML, pp 2791\u20132800"},{"key":"620_CR11","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions-I. Math Program 14:265\u2013294","journal-title":"Math Program"},{"key":"620_CR12","doi-asserted-by":"crossref","unstructured":"Sakaue S, Ishihata M (2018) Accelerated best-first search with upper-bound computation for submodular function maximization. In: Proceedings of AAAI, pp 1413\u20131421","DOI":"10.1609\/aaai.v32i1.11521"},{"key":"620_CR13","doi-asserted-by":"crossref","unstructured":"Sakaue S, Nishino M, Yasuda N (2018) Submodular function maximization over graphs via zero-suppressed binary decision diagrams. In: Proceedings of AAAI, pp 1422\u20131430","DOI":"10.1609\/aaai.v32i1.11520"},{"key":"620_CR14","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1287\/ijoc.2015.0660","volume":"28","author":"A Shioura","year":"2016","unstructured":"Shioura A, Shakhlevich NV, Strusevich VA (2016) Application of submodular optimization to single machine scheduling with controllable processing times subject to release dates and deadlines. INFORMS J Comput 28:148\u2013161","journal-title":"INFORMS J Comput"},{"key":"620_CR15","unstructured":"Soma T, Yoshida Y (2015) A generalization of submodular cover via the diminishing return property on the integer lattice. In: Proceedings of NIPS, pp 847\u2013855"},{"key":"620_CR16","doi-asserted-by":"crossref","unstructured":"Soma T, Yoshida Y (2017) Non-monotone DR-submodular function maximization. In: Proceedings of AAAI, pp 898\u2013904","DOI":"10.1609\/aaai.v31i1.10653"},{"key":"620_CR17","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 (2018) Maximizing monotone submodular functions over the integer lattice. Math Program 172:539\u2013563","journal-title":"Math Program"},{"key":"620_CR18","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 (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper Res Lett 32:41\u201343","journal-title":"Oper Res Lett"},{"key":"620_CR19","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1287\/moor.2016.0842","volume":"42","author":"M Sviridenko","year":"2017","unstructured":"Sviridenko M, Vondr\u00e1k J, Ward J (2017) Optimal approximation for submodular and supermodular optimization with bounded curvature. Math Oper Res 42:1197\u20131218","journal-title":"Math Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00620-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00620-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00620-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T17:58:11Z","timestamp":1657735091000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00620-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,17]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["620"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00620-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,17]]},"assertion":[{"value":"17 July 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}