{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T02:33:38Z","timestamp":1774406018702,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T00:00:00Z","timestamp":1583971200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T00:00:00Z","timestamp":1583971200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"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"}]},{"name":"the Fundamental Research Funds for the Central Universities."}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,5]]},"DOI":"10.1007\/s10878-020-00558-4","type":"journal-article","created":{"date-parts":[[2020,3,12]],"date-time":"2020-03-12T08:02:44Z","timestamp":1584000164000},"page":"1208-1220","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["A 1\/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice"],"prefix":"10.1007","volume":"39","author":[{"given":"Qingqin","family":"Nong","sequence":"first","affiliation":[]},{"given":"Jiazhu","family":"Fang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0587-6645","authenticated-orcid":false,"given":"Suning","family":"Gong","sequence":"additional","affiliation":[]},{"given":"Dingzhu","family":"Du","sequence":"additional","affiliation":[]},{"given":"Yan","family":"Feng","sequence":"additional","affiliation":[]},{"given":"Xiaoying","family":"Qu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,12]]},"reference":[{"issue":"1\u20132","key":"558_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s10107-009-0298-1","volume":"128","author":"S Ahmed","year":"2011","unstructured":"Ahmed S, Atamt\u00fcrk A (2011) Maximizing a class of submodular utility functions. Math Program 128(1\u20132):149\u2013169","journal-title":"Math Program"},{"issue":"1\u20132","key":"558_CR2","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s10107-018-1248-6","volume":"175","author":"F Bach","year":"2019","unstructured":"Bach F (2019) Submodular functions: from discrete to continuous domains. Math Program 175(1\u20132):419\u2013459","journal-title":"Math Program"},{"key":"558_CR3","unstructured":"Bian A, Mirzasoleiman B, Buhmann J, Krause A (2017) Guaranteed nonconvex optimization: Submodular maximization over continuous domains. In: Proceedings of the 20th international conference on artificial intelligence and statistics. JMLR. Fort Lauderdale, Florida, USA, pp 111\u2013120"},{"key":"558_CR4","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Feldman M (2018) Deterministic algorithms for submodular maximization problems. ACM Trans Algorithms 14(3): Article 32","DOI":"10.1145\/3184990"},{"key":"558_CR5","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Feldman M, Naor J-S, Schwartz R (2014) Submodular maximization with cardinality constraints. In: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms. SODA. Oregon, Portland, pp 1433\u20131452","DOI":"10.1137\/1.9781611973402.106"},{"issue":"5","key":"558_CR6","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/130929205","volume":"44","author":"N Buchbinder","year":"2015","unstructured":"Buchbinder N, Feldman M, Seffi J, Schwartz R (2015) A tight linear time (1\/2)-approximation for unconstrained submodular maximization. SIAM J Comput 44(5):1384\u20131402","journal-title":"SIAM J Comput"},{"key":"558_CR7","doi-asserted-by":"crossref","unstructured":"Ene A, Nguy$$\\tilde{\\hat{\\text{e}}}$$n H-L, (2016) Constrained submodular maximization: beyond $$1\/e$$. In: 2016 IEEE 57th annual symposium on foundations of computer science. FOCS. New Brunswick, NJ, USA, pp 248\u2013258","DOI":"10.1109\/FOCS.2016.34"},{"key":"558_CR8","unstructured":"Ene A, Nguy$$\\tilde{\\hat{\\text{e}}}$$n H-L, Vladu A (2018) A parallel double greedy algorithm for submodular maximization, arXiv:1812.01591"},{"issue":"4","key":"558_CR9","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 (2011) Maximizing non-monotone submodular functions. SIAM J Comput 40(4):1133\u20131153","journal-title":"SIAM J Comput"},{"key":"558_CR10","doi-asserted-by":"crossref","unstructured":"Feldman M, Naor J, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. In: 2011 IEEE 52nd annual symposium on foundations of computer science. FOCS. Palm Springs, CA, USA, pp 570\u2013579","DOI":"10.1109\/FOCS.2011.46"},{"key":"558_CR11","unstructured":"Gharan S-O, Vondr\u00e1k J (2011) Submodular maximization by simulated annealing. In: Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics. San Francisco, California, USA, pp 1098\u20131117"},{"key":"558_CR12","doi-asserted-by":"crossref","unstructured":"Gottschalk C, Peis B (2015) Submodular function maximization on the bounded integer lattice. In: Sanit\u00e1 L, Skutella M (eds) WAOA 2015, vol 9499. LNCS, Springer, Cham, pp 133\u2013144","DOI":"10.1007\/978-3-319-28684-6_12"},{"key":"558_CR13","doi-asserted-by":"crossref","unstructured":"Hartline J, Mirrokni V, Sundararajan M (2008) Optimal marketing strategies over social networks. In: Proceedings of the 17th international conference on World Wide Web. ACM, Beijing, China, pp 189\u2013198","DOI":"10.1145\/1367497.1367524"},{"key":"558_CR14","doi-asserted-by":"crossref","unstructured":"Kapralov M, Post I, Vondr\u00e1k J (2013) Online submodular welfare maximization: greedy is optimal. In: Proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms. SIAM. New Orleans, Louisiana, USA, pp 1216\u20131225","DOI":"10.1137\/1.9781611973105.88"},{"key":"558_CR15","unstructured":"Niazadeh R, Roughgarden T (2018) Optimal algorithms for continuous non-monotone submodular and DR-submodular maximization. In: the 32nd conference on neural information processing systems. NIPS. Montr\u00e9al, Canada, pp 9617\u20139627"},{"key":"558_CR16","unstructured":"Soma T, Yoshida Y (2015) A generalization of submodular cover via the diminishing return property on the integer lattice. In: Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R (eds) Advances in neural information processing systems 28. Curran Associates, Inc., pp 847\u2013855"},{"key":"558_CR17","doi-asserted-by":"crossref","unstructured":"Soma T, Yoshida Y (2017) Non-monotone dr-submodular function maximization. In: Proceedings of the 31st AAAI conference on artificial intelligence. AAAI. San Francisco, California, USA, pp 898\u2013904","DOI":"10.1609\/aaai.v31i1.10653"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00558-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-020-00558-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00558-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,18]],"date-time":"2022-10-18T13:53:08Z","timestamp":1666101188000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-020-00558-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,12]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["558"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00558-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,12]]},"assertion":[{"value":"12 March 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}