{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:46Z","timestamp":1740122386865,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":["12131003","11771386","11728104"],"award-info":[{"award-number":["12131003","11771386","11728104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Beijing Natural Science Foundation Project","award":["Z200002"],"award-info":[{"award-number":["Z200002"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12101587"],"award-info":[{"award-number":["12101587"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["06446"],"award-info":[{"award-number":["06446"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s10878-022-00978-4","type":"journal-article","created":{"date-parts":[[2023,1,11]],"date-time":"2023-01-11T18:02:42Z","timestamp":1673460162000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Two approximation algorithms for maximizing nonnegative weakly monotonic set functions"],"prefix":"10.1007","volume":"45","author":[{"given":"Min","family":"Cui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9100-9291","authenticated-orcid":false,"given":"Ruiqi","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,1,11]]},"reference":[{"issue":"1","key":"978_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):149\u2013169","journal-title":"Math Program"},{"issue":"6","key":"978_CR2","first-page":"1306","volume":"15","author":"G Attigeri","year":"2019","unstructured":"Attigeri G, Manohara PMM, Radhika MP (2019) Feature selection using submodular approach for financial big data. J Inform Process Syst 15(6):1306\u20131325","journal-title":"J Inform Process Syst"},{"key":"978_CR3","doi-asserted-by":"crossref","unstructured":"Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: massive data summarization on the fly. In: Proceedings of the 20th International Proceedings on Knowledge discovery and data mining, pp.671\u2013680","DOI":"10.1145\/2623330.2623637"},{"key":"978_CR4","unstructured":"Bian AA, Buhmann JM, Krause A, Tschiatschek S (2017) Guarantees for Greedy maximization of non-submodular functions with applications. In: Proceedings of the 35th International Conference on Machine Learning, 70: pp.498\u2013507"},{"issue":"5","key":"978_CR5","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/130929205","volume":"44","author":"N Buchbinder","year":"2015","unstructured":"Buchbinder N, Feldman M, Naor JS, Schwartz R (2015a) A tight linear time (1\/2)-approximation for unconstrained submodular maximization. SIAM J Comput 44(5):1384\u20131402","journal-title":"SIAM J Comput"},{"key":"978_CR6","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Feldman M, Schwartz R (2015b) Online submodular maximization with preemption. In: Proceedings of the 26th International Symposium on Discrete Algorithms, pp.1202\u20131216","DOI":"10.1137\/1.9781611973730.80"},{"key":"978_CR7","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Feldman M (2016) Deterministic algorithms for submodular maximization problems, In: Proceedings of the 27th International Symposium on Discrete Algorithms, pp.392\u2013403","DOI":"10.1137\/1.9781611974331.ch29"},{"key":"978_CR8","unstructured":"Cherenin V (1962) Solving some combinatorial problems of optimal planning by the method of successive calculations. In: Proceedings of Experiences and Perspectives of the Applications of Mathematical Methods and Electronic Computers in Planning"},{"key":"978_CR9","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1016\/j.cor.2016.09.008","volume":"78","author":"VN Coelho","year":"2017","unstructured":"Coelho VN, Oliveira TA, Coelho IM, Coelho BN, Fleming PJ, Guimar\u00e3es FG, Ramalhinho H, Souza MJF, Talbi E-G, Lust T (2017) Generic pareto local search metaheuristic for optimization of targeted offers in a bi-objective direct marketing campaign. Comput Oper Res 78:578\u2013587","journal-title":"Comput Oper Res"},{"key":"978_CR10","unstructured":"Das A, Kempe D (2011) Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection. In: Proceedings of the 28th International Conference on Machine Learning, pp.1057\u20131064"},{"key":"978_CR11","doi-asserted-by":"crossref","unstructured":"Dobzinski S, Vondrak J (2012) From query complexity to computational complexity. In: Proceedings of the 44th International Symposium on Theory of Computing, pp.1107\u20131116","DOI":"10.1145\/2213977.2214076"},{"key":"978_CR12","unstructured":"Dughmi S (2009) Submodular functions: Extensions, distributions, and algorithms. a survey, arXiv preprint arXiv:0912.0322"},{"issue":"4","key":"978_CR13","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige U, Mirrokni VS, Vondr\u00e1k J (2011) Maximizing non-monotone submodular functions. SIAM J Comput 40(4):1133\u20131153","journal-title":"SIAM J Comput"},{"key":"978_CR14","doi-asserted-by":"crossref","unstructured":"Feldman M, Naor J, Schwartz R (2011) Nonmonotone submodular maximization via a structural continuous greedy algorithm. In: Proceedings of the 38th International Colloquium Conference on Automata, Languages and Programming, 6755, pp.342\u2013353","DOI":"10.1007\/978-3-642-22006-7_29"},{"issue":"1","key":"978_CR15","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.tcs.2007.05.036","volume":"385","author":"G Galbiati","year":"2007","unstructured":"Galbiati G, Maffioli F (2007) Approximation algorithms for maximum cut with limited unbalance. Theoret Comput Sci 385(1):78\u201387","journal-title":"Theoret Comput Sci"},{"key":"978_CR16","doi-asserted-by":"crossref","unstructured":"Gharan SO, Vondr\u00e1k J (2011) Submodular maximization by simulated annealing. In: Proceedings of the 22nd International Symposium on Discrete Algorithms, pp.1098\u20131116","DOI":"10.1137\/1.9781611973082.83"},{"issue":"1","key":"978_CR17","first-page":"427","volume":"42","author":"D Golovin","year":"2010","unstructured":"Golovin D, Krause A (2010) Adaptive submodularity: theory and applications in active learning and stochastic optimization. J Artif Intell Res 42(1):427\u2013486","journal-title":"J Artif Intell Res"},{"issue":"3","key":"978_CR18","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1007\/s10898-019-00800-2","volume":"75","author":"S Gong","year":"2019","unstructured":"Gong S, Nong Q, Liu W, Fang Q (2019) Parametric monotone function maximization with matroid constraints. J Global Optim 75(3):833\u2013849","journal-title":"J Global Optim"},{"key":"978_CR19","unstructured":"Halperin E, Zwick U (2001) Combinatorial approximation algorithms for the maximum directed cut problem. In: Proceedings of the 12th International Symposium on Discrete Algorithms, pp. 1\u20137"},{"key":"978_CR20","doi-asserted-by":"crossref","unstructured":"Hartline J, Mirrokni V, Sundararajan M (2008) Optimal marketing strategies over social networks. In: Proceedings of the 17th International Proceedings on World Wide Web, pp.189\u2013198","DOI":"10.1145\/1367497.1367524"},{"key":"978_CR21","first-page":"2903","volume":"13","author":"E Hazan","year":"2012","unstructured":"Hazan E, Kale S (2012) Online submodular minimization. J Mach Learn Res 13:2903\u20132922","journal-title":"J Mach Learn Res"},{"key":"978_CR22","unstructured":"Jegelka S, Bilmes JA (2011) Online Submodular Minimization for Combinatorial Structures. In: Proceedings of the 28th International Conference on Machine Learning, pp.345\u2013352"},{"issue":"2","key":"978_CR23","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/j.patrec.2010.08.008","volume":"42","author":"Y Kawahara","year":"2011","unstructured":"Kawahara Y, Nagano K, Okamoto Y (2011) Submodular fractional programming for balanced clustering. Pattern Recogn Lett 42(2):235\u2013243","journal-title":"Pattern Recogn Lett"},{"issue":"1","key":"978_CR24","doi-asserted-by":"publisher","first-page":"105","DOI":"10.4086\/toc.2015.v011a004","volume":"11","author":"D Kempe","year":"2015","unstructured":"Kempe D, Kleinberg J, Tardos E (2015) Maximizing the spread of influence through a social network. Theory Comput 11(1):105\u2013147","journal-title":"Theory Comput"},{"key":"978_CR25","unstructured":"Krause A, Guestrin C (2007) Near-optimal observation selection using submodular functions. In: Proceedings of the 22nd International Conference on Artificial Intelligence, 7, pp.1650\u20131654"},{"key":"978_CR26","doi-asserted-by":"crossref","unstructured":"Lin Y, Chen W, Lui JC (2017) Boosting Information Spread: An Algorithmic Approach. In: Proceedings of the International Conference on Data Engineering, pp.883\u2013894","DOI":"10.1109\/ICDE.2017.137"},{"key":"978_CR27","unstructured":"Mansell R, Collins BS (2005) Introduction: Trust and crime in information societies. Edward Elgar, pp. 1\u201310"},{"issue":"2","key":"978_CR28","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/j.ejor.2008.05.007","volume":"196","author":"MT Melo","year":"2009","unstructured":"Melo MT, Nickel S, Saldanha-da-Gama F (2009) Facility location and supply chain management-a review. Eur J Oper Res 196(2):401\u2013412","journal-title":"Eur J Oper Res"},{"key":"978_CR29","doi-asserted-by":"crossref","unstructured":"Milgrom P, Milgrom PR (2004) Putting auction theory to work. Cambridge University Press","DOI":"10.1017\/CBO9780511813825"},{"key":"978_CR30","doi-asserted-by":"crossref","unstructured":"Mossel E, Roch S (2007) On the submodularity of influence in social networks. In: Proceedings of the 30th International Symposium on Theory of Computing, pp.128\u2013134","DOI":"10.1145\/1250790.1250811"},{"key":"978_CR31","unstructured":"Parambath SA, Chawla S, Vijayakumar N (2018) SAGA: A Submodular Greedy Algorithm for Group Recommendation, In: Proceedings of International Conference on Artificial Intelligence, pp.3900\u20133908"},{"key":"978_CR32","unstructured":"Roughgarden T, Wang J (2018) An Optimal Learning Algorithm for Online Unconstrained Submodular Maximization. In: Proceedings of the 31st International Conference on Learning Theory, 75, pp.1307\u20131325"},{"key":"978_CR33","doi-asserted-by":"crossref","unstructured":"Streeter M, Golovin D (2008) An online algorithm for maximizing submodular functions. In: Proceedings of the 22nd International Conference on Neural Information Processing Systems, pp.1577\u20131584","DOI":"10.21236\/ADA476748"},{"issue":"24","key":"978_CR34","doi-asserted-by":"publisher","first-page":"5474","DOI":"10.3390\/s19245474","volume":"19","author":"AK Tran","year":"2019","unstructured":"Tran AK, Piran MJ, Pham C (2019) SDN controller placement in IoT networks: an optimized submodularity-based approach. Sensors 19(24):5474","journal-title":"Sensors"},{"issue":"9","key":"978_CR35","doi-asserted-by":"publisher","first-page":"2591","DOI":"10.3390\/s20092591","volume":"20","author":"Y-C Tsai","year":"2020","unstructured":"Tsai Y-C, Tseng K-S (2020) Deep compressed sensing for learning submodular functions. Sensors 20(9):2591","journal-title":"Sensors"},{"key":"978_CR36","unstructured":"Wei K, Iyer R, Bilmes JA (2015) Submodularity in data subset selection and active learning. In: Proceedings of the 32nd International Conference on Machine Learning, 37, pp.1954\u20131963"},{"key":"978_CR37","doi-asserted-by":"crossref","unstructured":"Zhang H, Vorobeychik Y (2016) Submodular optimization with routing constraints. In: Proceedings of the 30th International Proceedings on Artificial Intelligence, pp. 819\u2013825","DOI":"10.1609\/aaai.v30i1.10066"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00978-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00978-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00978-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,4]],"date-time":"2023-02-04T07:53:25Z","timestamp":1675497205000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00978-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["978"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00978-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2023,1]]},"assertion":[{"value":"22 December 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 January 2023","order":2,"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 not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"54"}}