{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:14Z","timestamp":1740122354263,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T00:00:00Z","timestamp":1615420800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T00:00:00Z","timestamp":1615420800000},"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":["11971447","11871442"],"award-info":[{"award-number":["11971447","11871442"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100012226","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":[[2022,7]]},"DOI":"10.1007\/s10878-021-00717-1","type":"journal-article","created":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T09:12:30Z","timestamp":1615453950000},"page":"1655-1670","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast algorithms for maximizing monotone nonsubmodular functions"],"prefix":"10.1007","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8958-3999","authenticated-orcid":false,"given":"Bin","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miaomiao","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,11]]},"reference":[{"issue":"3","key":"717_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 AA, Sviridenko MI (2004) Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J Combinatorial Optim 8(3):307\u2013328","journal-title":"J Combinatorial Optim"},{"key":"717_CR2","unstructured":"N. Alaluf, A. Ene, M. Feldman, H. Nguyen, A. Suh, Optimal Streaming Algorithms for Submodular Maximization with Cardinality Constraints. In LIPI (2020)"},{"key":"717_CR3","doi-asserted-by":"crossref","unstructured":"Badanidiyuru A, Mirzasoleiman B, Karbasi A et al (2014) Streaming Submodular Maximization: Massive AData Summarization on the Fly. ACM 671\u2013680","DOI":"10.1145\/2623330.2623637"},{"key":"717_CR4","doi-asserted-by":"crossref","unstructured":"Badanidiyuru A, Vondr\u00e1k J (2014) Fast Algorithm for Maximizing Submodular Functions. SODA 1497\u20131514","DOI":"10.1137\/1.9781611973402.110"},{"key":"717_CR5","unstructured":"Balkanski E, Breuer A, Singer Y (2018) Non-monotone Submodular Maximization in Exponentially Fewer Iterations. NIPS 2353\u20132364"},{"key":"717_CR6","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. SODA 283\u2013302","DOI":"10.1137\/1.9781611975482.19"},{"key":"717_CR7","doi-asserted-by":"crossref","unstructured":"Balkanski E, Singer Y (2018) The Adaptive Complexity of Maximizing a Submodular Function. STOC 1138\u20131151","DOI":"10.1145\/3188745.3188752"},{"key":"717_CR8","unstructured":"A. A. Bian, J. M. Buhmann, A. Krause, S. Tschiatschek, Guarantees for Greedy Maximization of Nonsubmodular Functions with Applications. In ICML (2017)"},{"key":"717_CR9","unstructured":"Breuer A, Balkanski E, Singer Y (2020) The FAST Algorithm for Submodular Maximization. ICML 1134\u20131143"},{"issue":"3","key":"717_CR10","first-page":"1","volume":"14","author":"N Buchbinder","year":"2018","unstructured":"Buchbinder N, Feldman M (2018) Deterministic algorithms for submodular maximization problems. ACM 14(3):1\u201320","journal-title":"ACM"},{"issue":"3","key":"717_CR11","doi-asserted-by":"publisher","first-page":"988","DOI":"10.1287\/moor.2018.0955","volume":"44","author":"N Buchbinder","year":"2019","unstructured":"Buchbinder N, Feldman M (2019) Constrained submodular maximization via a nonsymmetric technique. Math Op Res 44(3):988\u20131005","journal-title":"Math Op Res"},{"key":"717_CR12","doi-asserted-by":"crossref","unstructured":"Calinescu G, Chekuri C, P\u00e1l M, Vondr\u00e1k J (2007) Maximizing a Submodular Set Function Subject to a Matroid Constraint. IPCO 182\u2013196","DOI":"10.1007\/978-3-540-72792-7_15"},{"key":"717_CR13","doi-asserted-by":"crossref","unstructured":"Chekuri C, Vondr\u00e1k J, Zenklusen R (2011) Submodular Function Maximization Via the Multilinear Relaxation and Contention Resolution Schemes. STOC 783\u2013792","DOI":"10.1145\/1993636.1993740"},{"issue":"3","key":"717_CR14","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-Edmonds theorem. Discret Appl Math 7(3):251\u2013274","journal-title":"Discret Appl Math"},{"key":"717_CR15","unstructured":"Das A, David K (2011) Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection. ICML 1057\u20131064"},{"key":"717_CR16","first-page":"11","volume":"2570","author":"J Edmonds","year":"2003","unstructured":"Edmonds J (2003) Submodular functions, matroids, and certain polyhedra. LNCS 2570:11\u201326","journal-title":"LNCS"},{"issue":"6B","key":"717_CR17","doi-asserted-by":"publisher","first-page":"3539","DOI":"10.1214\/17-AOS1679","volume":"46","author":"ER Elenberg","year":"2018","unstructured":"Elenberg ER, Khanna R, Dimakis AG, Negahban S (2018) Restricted strong convexity implies weak submodularity. Annals Stat 46(6B):3539\u20133568","journal-title":"Annals Stat"},{"key":"717_CR18","doi-asserted-by":"crossref","unstructured":"Ene A, Nguyen HL (2019) Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time. SODA 274\u2013282","DOI":"10.1137\/1.9781611975482.18"},{"key":"717_CR19","doi-asserted-by":"crossref","unstructured":"Fahrbach M, Mirrokni V, Zadimoghaddam M (2019) Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity. PMLR 1833\u20131842","DOI":"10.1137\/1.9781611975482.17"},{"key":"717_CR20","doi-asserted-by":"crossref","unstructured":"U. Feige, R. Izsak, Welfare Maximization and the Supermodular Degree. In ITCS(2013), 247\u2013256","DOI":"10.1145\/2422436.2422466"},{"issue":"4","key":"717_CR21","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of $$\\ln n$$ for approximating set cover. JACM 45(4):634\u2013652","journal-title":"JACM"},{"issue":"4","key":"717_CR22","first-page":"1133","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige U, Mirrokni VS, Vondr\u00e1k J (2011) Maximizing non-monotone submodular functions. J Comput 40(4):1133\u20131153","journal-title":"J Comput"},{"key":"717_CR23","first-page":"160","volume":"I","author":"M Feldman","year":"2014","unstructured":"Feldman M, Izsak R (2014) Constrained monotone function maximization and the supermodular degree. LIP I:160\u2013175","journal-title":"LIP"},{"key":"717_CR24","doi-asserted-by":"crossref","unstructured":"Feldman M, Norouzi-Fard A, Svensson O, Zenklusen R (2020) The One-way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness. STOC 1363\u20131374","DOI":"10.1145\/3357713.3384286"},{"issue":"3","key":"717_CR25","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) So parametric monotone function maximization with matroid constraints. J Glob Optim 75(3):833\u2013849","journal-title":"J Glob Optim"},{"key":"717_CR26","unstructured":"Gotovos A, Karbasi A, Krause A (2015) Non-Monotone Adaptive Submodular Maximization. In IJCA I:1996\u20132003"},{"key":"717_CR27","unstructured":"Iyer R, Bilmes J (2012) Algorithms for Approximate Minimization of the Difference between Submodular Functions, with Applications. UAI 407\u2013417"},{"issue":"2","key":"717_CR28","first-page":"1","volume":"14","author":"Y Jiang","year":"2019","unstructured":"Jiang Y, Wang Y, Xu D, Yang R, Zhang Y (2019) Streaming algorithm for maximizing a monotone non-submodular function under D-knapsack constraint. Optim Lett 14(2):1\u201314","journal-title":"Optim Lett"},{"key":"717_CR29","unstructured":"E. Kazemi, M. Mitrovic, Zadimoghaddam, S. Lattanzi, A. Karbasi, Submodular Streaming in all its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity. In ICML (2019) 5767\u20135784"},{"key":"717_CR30","doi-asserted-by":"crossref","unstructured":"A. Kohara, K. Okano, K. Hirata, et\u00a0al. Sensor Placement Minimizing the State Estimation Mean Square Error: Performance Guarantees of Greedy Solutions (2020). arXiv:2004.04355","DOI":"10.1109\/CDC42340.2020.9304166"},{"key":"717_CR31","unstructured":"Kuhnle A, Smith JD, Crawford VG, Thai MT (2018) Fast maximization of Non-submodular, Monotonic Functions on the Integer Lattice. ICML 2791\u20132800"},{"key":"717_CR32","doi-asserted-by":"crossref","unstructured":"Li M, Zhou X, Tan J, Wang W (2020) Non-Submodular Streaming Maximization with Minimum Memory and Low Adaptive Complexity. LNCS 214\u2013224","DOI":"10.1007\/978-3-030-57602-8_20"},{"issue":"1\u20132","key":"717_CR33","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s10107-014-0792-y","volume":"152","author":"T Maehara","year":"2015","unstructured":"Maehara T, Murota K (2015) A framework of discrete DC programming by discrete convex analysis. Math Programm 152(1\u20132):435\u2013466","journal-title":"Math Programm"},{"key":"717_CR34","unstructured":"B. Mirzasoleiman, A. Karbasi, R. Sarkar, A. Sarkar, Distributed Submodular Maximization: Identifying Representative Elements in Massive Datas. In NIPS (2013)"},{"key":"717_CR35","first-page":"1812","volume":"I","author":"B Mirzasoleiman","year":"2015","unstructured":"Mirzasoleiman B, Badanidiyuru A, Karbasi A, Vondr\u00e1k J, Krause A (2015) Lazier Than Lazy Greedy. In AAA I:1812\u20131818","journal-title":"Lazier Than Lazy Greedy. In AAA"},{"key":"717_CR36","unstructured":"Narasimhan M, Bilmes JA (2005) A Submodular-Supermodular Procedure with Applications to Discriminative Structure Learning. UA I:404\u2013412"},{"issue":"3","key":"717_CR37","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 functions. Math Op Res 3(3):177\u2013188","journal-title":"Math Op Res"},{"issue":"1","key":"717_CR38","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 Programm 14(1):265\u2013294","journal-title":"Math Programm"},{"key":"717_CR39","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.05.018","author":"Q Nong","year":"2020","unstructured":"Nong Q, Sun T, Gong S, Sun T, Fang Q, Du D, Shao X (2020) Maximize a monotone function with a generic submodularity ratio. Theor Computer Sci. https:\/\/doi.org\/10.1016\/j.tcs.2020.05.018","journal-title":"Theor Computer Sci"},{"key":"717_CR40","unstructured":"R. Santiago, Y. Yoshida, Weakly Submodular Function Maximization Using Local Submodularity Ratio(2020). arXiv:2004.14650"},{"issue":"1","key":"717_CR41","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. Op Res Lett 32(1):41\u201343","journal-title":"Op Res Lett"},{"issue":"4","key":"717_CR42","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 Op Res 42(4):1197\u20131218","journal-title":"Math Op Res"},{"key":"717_CR43","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k J (2008) Optimal Approximation for the Submodular Welfare Problem in the Value Oracle Model. STOC 67\u201374","DOI":"10.1145\/1374376.1374389"},{"key":"717_CR44","first-page":"253","volume":"23","author":"J Vondr\u00e1k","year":"2010","unstructured":"Vondr\u00e1k J (2010) Submodularity and curvature: the optimal algorithm. RIMS Kokyuroku Bessatsu B 23:253\u2013266","journal-title":"RIMS Kokyuroku Bessatsu B"},{"key":"717_CR45","first-page":"1","volume":"30","author":"Y Wang","year":"2019","unstructured":"Wang Y, Xu D, Wang Y, Zhang D (2019) Non-submodular maximization on massive data streams. J Glob Optim 30:1\u201315","journal-title":"J Glob Optim"},{"issue":"1","key":"717_CR46","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s10107-018-1242-z","volume":"169","author":"C Wu","year":"2018","unstructured":"Wu C, Wang Y, Lu Z et al (2018) Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming. Math Programm 169(1):255\u2013275","journal-title":"Math Programm"},{"issue":"2","key":"717_CR47","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s40305-018-0233-3","volume":"7","author":"W Wu","year":"2019","unstructured":"Wu W, Zhang Z, Du D (2019) Set function optimization. J Op Res Soc Chin 7(2):183\u2013193","journal-title":"J Op Res Soc Chin"},{"key":"717_CR48","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. Computing and Combinatorics 651\u2013662","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-00717-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00717-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00717-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T18:03:26Z","timestamp":1657735406000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00717-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,11]]},"references-count":48,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["717"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00717-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,3,11]]},"assertion":[{"value":"22 February 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 March 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}