{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:01Z","timestamp":1759637881955,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T00:00:00Z","timestamp":1615766400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T00:00:00Z","timestamp":1615766400000},"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","11871081"],"award-info":[{"award-number":["11531014","11871081"]}],"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":["11701150","61772005"],"award-info":[{"award-number":["11701150","61772005"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003392","name":"Natural Science Foundation of Fujian Province","doi-asserted-by":"publisher","award":["2017J01753"],"award-info":[{"award-number":["2017J01753"]}],"id":[{"id":"10.13039\/501100003392","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Outstanding Youth Innovation Team Project for Universities of Shandong Province","award":["2020KJN008"],"award-info":[{"award-number":["2020KJN008"]}]}],"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-021-00719-z","type":"journal-article","created":{"date-parts":[[2021,3,15]],"date-time":"2021-03-15T20:12:32Z","timestamp":1615839152000},"page":"1671-1690","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximation guarantees for parallelized maximization of monotone non-submodular function with a cardinality constraint"],"prefix":"10.1007","volume":"43","author":[{"given":"Min","family":"Cui","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2891-4253","authenticated-orcid":false,"given":"Longkun","family":"Guo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,15]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Agarwal A, Assadi S, Khanna S (2019) Stochastic submodular cover with limited adaptivity. In: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, pp 323\u2013342","key":"719_CR1","DOI":"10.1137\/1.9781611975482.21"},{"key":"719_CR2","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154","volume-title":"The probabilistic method","author":"N Alon","year":"2000","unstructured":"Alon N, Spencer J (2000) The probabilistic method. Wiley, New York"},{"issue":"6","key":"719_CR3","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 Inf Process Syst 15(6):1306\u20131325","journal-title":"J Inf Process Syst"},{"doi-asserted-by":"crossref","unstructured":"Balkanski E, Rubinstein A, Singer Y (2019) An exponential speedup in parallel running time for submodular maximization without loss in approximation. In: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, pp 283\u2013302","key":"719_CR4","DOI":"10.1137\/1.9781611975482.19"},{"doi-asserted-by":"crossref","unstructured":"Balkanski E, Singer Y (2018) The adaptive complexity of maximizing a submodular function. In: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pp 1138\u20131151","key":"719_CR5","DOI":"10.1145\/3188745.3188752"},{"doi-asserted-by":"crossref","unstructured":"Balkanski E, Singer Y (2020) A lower bound for parallel submodular minimization. In: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, pp 130\u2013139","key":"719_CR6","DOI":"10.1145\/3357713.3384287"},{"unstructured":"Bian AA, Buhmann JM, Krause A, Tschiatschek S (2017) Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of the 34th international proceedings on international conference on machine learning, vol 70, pp 498\u2013507","key":"719_CR7"},{"unstructured":"Breuer A, Balkanski E, Singer Y (2020) The FAST algorithm for submodular maximization. In: Proceedings of the 37th international conference on machine learning, pp 1134\u20131143","key":"719_CR8"},{"issue":"5","key":"719_CR9","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/130929205","volume":"44","author":"N Buchbinder","year":"2015","unstructured":"Buchbinder N, Feldman M, Naor 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"},{"doi-asserted-by":"crossref","unstructured":"Chekuri C, Quanrud K (2019a) Submodular function maximization in parallel via the multilinear relaxation. In: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, pp 303\u2013322","key":"719_CR10","DOI":"10.1137\/1.9781611975482.20"},{"doi-asserted-by":"crossref","unstructured":"Chekuri C, Quanrud K (2019b) Parallelizing greedy for submodular set function maximization in matroids and beyond. In: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pp 78\u201389","key":"719_CR11","DOI":"10.1145\/3313276.3316406"},{"issue":"4","key":"719_CR12","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H Chernoff","year":"1952","unstructured":"Chernoff H (1952) A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann Math Stat 23(4):493\u2013507","journal-title":"Ann Math Stat"},{"doi-asserted-by":"crossref","unstructured":"Ene A, Nguyen HL (2019) Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, pp 274\u2013282","key":"719_CR13","DOI":"10.1137\/1.9781611975482.18"},{"doi-asserted-by":"crossref","unstructured":"Ene A, Nguyn HL, Vladu A (2019) Submodular maximization with matroid and packing constraints in parallel. In: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pp 90\u2013101","key":"719_CR14","DOI":"10.1145\/3313276.3316389"},{"unstructured":"Ene A, Nguyn HL (2020) Parallel algorithm for non-monotone DR-submodular maximization. In: Proceedings of the 37th international conference on machine learning, pp 2902\u20132911","key":"719_CR15"},{"doi-asserted-by":"crossref","unstructured":"Fahrbach M, Miller GL, Peng R, Sawlani S, Wang J, Xu SC (2018) Graph sketching against adaptive adversaries applied to the minimum degree algorithm. In: Proceedings of the 59th annual symposium on foundations of computer science, pp 101\u2013112","key":"719_CR16","DOI":"10.1109\/FOCS.2018.00019"},{"doi-asserted-by":"crossref","unstructured":"Fahrbach M, Mirrokni V, Zadimoghaddam M (2019) Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, pp 255\u2013273","key":"719_CR17","DOI":"10.1137\/1.9781611975482.17"},{"issue":"4","key":"719_CR18","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige U, Mirrokni V, Vondrak J (2011) Maximizing non-monotone submodular functions. SIAM J Comput 40(4):1133\u20131153","journal-title":"SIAM J Comput"},{"issue":"1","key":"719_CR19","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":"719_CR20","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"},{"issue":"2","key":"719_CR21","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":"719_CR22","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"},{"unstructured":"Kuhnle A, Smith J, Crawford VG, Thai MT (2018) Fast maximization of non-submodular, monotonic functions on the integer lattice. In: Proceedings of the 35th international proceedings on international conference on machine learning, pp 2786\u20132795","key":"719_CR23"},{"doi-asserted-by":"crossref","unstructured":"Kuhnle A (2021) Nearly linear-time, parallelizable algorithms for non-monotone submodular maximization. In: Proceedings of the 35th AAAI conference on artificial intelligence","key":"719_CR24","DOI":"10.1609\/aaai.v35i9.16998"},{"unstructured":"Lin H, Bilmes JA (2011) A class of submodular functions for document summarization. In: Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies, vol 1, pp 510\u2013520","key":"719_CR25"},{"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","key":"719_CR26","DOI":"10.1109\/ICDE.2017.137"},{"doi-asserted-by":"crossref","unstructured":"Mirrokni V, Zadimoghaddam M (2015) Randomized composable core-sets for distributed submodular maximization. In: Proceedings of the 47th annual ACM symposium on theory of computing, pp 153\u2013162","key":"719_CR27","DOI":"10.1145\/2746539.2746624"},{"issue":"1","key":"719_CR28","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(1):265\u2013294","journal-title":"Math Program"},{"issue":"3","key":"719_CR29","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Math Oper Res 3(3):177\u2013188","journal-title":"Math Oper Res"},{"doi-asserted-by":"crossref","unstructured":"Nong Q, Sun T, Gong S, Fang Q, Du D, Shao X (2019) Maximize a monotone function with a generic submodularity ratio. In: Proceedings of the international proceedings on algorithmic applications in management, pp 249\u2013260","key":"719_CR30","DOI":"10.1007\/978-3-030-27195-4_23"},{"unstructured":"Pan X, Jegelka S, Gonzalez JE, Bradley JK, Jordan MI (2014) Parallel double greedy submodular maximization. In: Proceedings of the 27th international conference on neural information processing systems, vol 1, pp 118\u2013126","key":"719_CR31"},{"doi-asserted-by":"crossref","unstructured":"Parambath SA, Chawla S, Vijayakumar N (2018) SAGA: a submodular greedy algorithm for group recommendation. In: Proceedings of international conference on international conference on artificial intelligence, pp 3900\u20133908","key":"719_CR32","DOI":"10.1609\/aaai.v32i1.11650"},{"key":"719_CR33","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.tcs.2020.11.007","volume":"850","author":"S Tang","year":"2021","unstructured":"Tang S (2021) Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time. Theor Comput Sci 850:249\u2013261","journal-title":"Theor Comput Sci"},{"unstructured":"Wei K, Iyer R, Bilmes JA (2015) Submodularity in data subset selection and active learning. In: Proceedings of the 32nd international conference on international conference on machine learning, vol 37, pp 1954\u20131963","key":"719_CR34"},{"doi-asserted-by":"crossref","unstructured":"Zhang Z, Liu B, Wang Y, Xu D, Zhang D (2019) Greedy algorithm for maximization of non-submodular functions subject to knapsack constraint. In: Proceedings of the international proceedings on computing and combinatorics conference, pp 651\u2013662","key":"719_CR35","DOI":"10.1007\/978-3-030-26176-4_54"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00719-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00719-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00719-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,21]],"date-time":"2022-12-21T15:32:46Z","timestamp":1671636766000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00719-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,15]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["719"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00719-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,3,15]]},"assertion":[{"value":"1 March 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 March 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}