{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:46:07Z","timestamp":1740123967820,"version":"3.37.3"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T00:00:00Z","timestamp":1702857600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T00:00:00Z","timestamp":1702857600000},"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":["12171444"],"award-info":[{"award-number":["12171444"]}],"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"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2024,1]]},"DOI":"10.1007\/s10957-023-02353-7","type":"journal-article","created":{"date-parts":[[2023,12,18]],"date-time":"2023-12-18T14:02:16Z","timestamp":1702908136000},"page":"194-214","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Algorithms for Cardinality-Constrained Monotone DR-Submodular Maximization with Low Adaptivity and Query Complexity"],"prefix":"10.1007","volume":"200","author":[{"given":"Suning","family":"Gong","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0895-7793","authenticated-orcid":false,"given":"Qingqin","family":"Nong","sequence":"additional","affiliation":[]},{"given":"Jiazhu","family":"Fang","sequence":"additional","affiliation":[]},{"given":"Ding-Zhu","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,18]]},"reference":[{"key":"2353_CR1","first-page":"39","volume":"65","author":"A Agarwal","year":"2017","unstructured":"Agarwal, A., Agarwal, S., Assadi, S., Khanna, S.: Learning with limited rounds of adaptivity: coin tossing, multi-armed bandits, and ranking from pairwise comparisons. Conf. Learn. Theory 65, 39\u201375 (2017)","journal-title":"Conf. Learn. Theory"},{"issue":"10","key":"2353_CR2","doi-asserted-by":"publisher","first-page":"6030","DOI":"10.1287\/mnsc.2020.3820","volume":"67","author":"S Alaei","year":"2021","unstructured":"Alaei, S., Makhdoumi, A., Malekian, A.: Maximizing sequence-submodular functions and its application to online advertising. Manag. Sci. 67(10), 6030\u20136054 (2021)","journal-title":"Manag. Sci."},{"key":"2353_CR3","doi-asserted-by":"publisher","first-page":"6195","DOI":"10.1109\/TSP.2021.3125147","volume":"69","author":"M Amiridi","year":"2021","unstructured":"Amiridi, M., Kargas, N., Sidiropoulos, N.D.: Information-theoretic feature selection via tensor decomposition and submodularity. IEEE Trans. Signal Process. 69, 6195\u20136205 (2021)","journal-title":"IEEE Trans. Signal Process."},{"doi-asserted-by":"crossref","unstructured":"Anari, N., Goel, G., Nikzad, A.: Mechanism design for crowdsourcing: an optimal $$1-1\/e$$ competitive budget-feasible mechanism for large markets. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science (FOCS), pp. 266\u2013275 (2014)","key":"2353_CR4","DOI":"10.1109\/FOCS.2014.36"},{"unstructured":"Asadpour, A., Niazadeh, R., Saberi A., Shameli, A.: Sequential submodular maximization and applications to ranking an assortment of products. Chicago Booth Research Paper 20-26 (2020)","key":"2353_CR5"},{"doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Mirzasoleiman, B., Karbasi A., Krause, A.: Streaming submodular maximization: massive data summarization on the fly. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 671\u2013680 (2014)","key":"2353_CR6","DOI":"10.1145\/2623330.2623637"},{"doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 497\u20131514 (2014)","key":"2353_CR7","DOI":"10.1137\/1.9781611973402.110"},{"key":"2353_CR8","first-page":"2353","volume":"31","author":"E Balkanski","year":"2018","unstructured":"Balkanski, E., Breuer, A., Singer, Y.: Non-monotone submodular maximization in exponentially fewer iterations. Adv. Neural. Inf. Process. Syst. 31, 2353\u20132364 (2018)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"doi-asserted-by":"crossref","unstructured":"Balkanski, E., Rubinstein, A., Singer, Y.: 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 (SODA), pp. 283\u2013302 (2019)","key":"2353_CR9","DOI":"10.1137\/1.9781611975482.19"},{"doi-asserted-by":"crossref","unstructured":"Balkanski, E., Rubinstein, A., Singer, Y.: An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 66\u201377 (2019)","key":"2353_CR10","DOI":"10.1145\/3313276.3316304"},{"doi-asserted-by":"crossref","unstructured":"Balkanski, E., Singer, Y.: The adaptive complexity of maximizing a submodular function. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 1138\u20131151 (2018)","key":"2353_CR11","DOI":"10.1145\/3188745.3188752"},{"unstructured":"Barbosa, R., Ene, A., Nguyen, H.L., Ward, J.: The power of randomization: Distributed submodular maximization on massive datasets. In: Proceedings of the 32nd International Conference on Machine Learning, vol. 37, pp. 1236\u20131244 (2015)","key":"2353_CR12"},{"doi-asserted-by":"crossref","unstructured":"Braverman, M., Mao, J., Weinberg, S.M.: Parallel algorithms for select and partition with noisy comparisons. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pp. 851\u2013862 (2016)","key":"2353_CR13","DOI":"10.1145\/2897518.2897642"},{"key":"2353_CR14","first-page":"1134","volume":"119","author":"A Breuer","year":"2020","unstructured":"Breuer, A., Balkanski, E., Singer, Y.: The FAST algorithm for submodular maximization. Int. Conf. Mach. Learn. (PMLR) 119, 1134\u20131143 (2020)","journal-title":"Int. Conf. Mach. Learn. (PMLR)"},{"doi-asserted-by":"crossref","unstructured":"Chekuri, C., Quanrud, K.: Submodular function maximization in parallel via the multilinear relaxation. In: Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 303\u2013322 (2019)","key":"2353_CR15","DOI":"10.1137\/1.9781611975482.20"},{"key":"2353_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3213772","volume":"65","author":"X Chen","year":"2018","unstructured":"Chen, X., Servedio, R.A., Tan, L.Y., Waingarten, E., Xie, J.: Settling the query complexity of non-adaptive junta testing. J. ACM 65, 1\u201318 (2018)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Das, A., Kempe, D.: Algorithms for subset selection in linear regression. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 45\u201354 (2008)","key":"2353_CR17","DOI":"10.1145\/1374376.1374384"},{"key":"2353_CR18","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1327452.1327492","volume":"51","author":"J Dean","year":"2008","unstructured":"Dean, J., Ghemawat, S.: Mapreduce: simplified data processing on large clusters. Commun. ACM 51, 107\u2013113 (2008)","journal-title":"Commun. ACM"},{"doi-asserted-by":"crossref","unstructured":"El-Arini, K., Guestrin, C.: Beyond keyword search: discovering relevant scientific literature. In: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 439\u2013447 (2011)","key":"2353_CR19","DOI":"10.1145\/2020408.2020479"},{"unstructured":"Ene, A., Nguyen, H.L.: A nearly-linear time algorithm for submodular maximization with a knapsack constraint. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP), vol. 132, pp. 53:1\u201353:12 (2019)","key":"2353_CR20"},{"unstructured":"Ene, A., Nguyen, H.L.: A reduction for optimizing lattice submodular functions with diminishing returns. arXiv:1606.08362 (2016)","key":"2353_CR21"},{"doi-asserted-by":"crossref","unstructured":"Ene, A., Nguyen, H.L.: Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 274\u2013282 (2019)","key":"2353_CR22","DOI":"10.1137\/1.9781611975482.18"},{"doi-asserted-by":"crossref","unstructured":"Epasto, A., Mirrokni, V., Zadimoghaddam, M.: Bicriteria distributed submodular maximization in a few rounds. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 25\u201333 (2017)","key":"2353_CR23","DOI":"10.1145\/3087556.3087574"},{"doi-asserted-by":"crossref","unstructured":"Fahrbach, M., Mirrokni, V., Zadimoghaddam, M.: Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In: Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 255\u2013273 (2019)","key":"2353_CR24","DOI":"10.1137\/1.9781611975482.17"},{"key":"2353_CR25","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.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40, 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"key":"2353_CR26","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2020.113392","volume":"152","author":"A Ghadimi","year":"2020","unstructured":"Ghadimi, A., Beigy, H.: Deep submodular network: an application to multi-document summarization. Expert Syst. Appl. 152, 113392 (2020)","journal-title":"Expert Syst. Appl."},{"key":"2353_CR27","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s10898-022-01193-5","volume":"85","author":"S Gong","year":"2023","unstructured":"Gong, S., Nong, Q., Bao, S., Fang, Q., Ding, D.-Z.: A fast and deterministic algorithm for Knapsack-constrained monotone DR-submodular maximization over an integer lattice. J. Glob. Optim. 85, 15\u201338 (2023)","journal-title":"J. Glob. Optim."},{"doi-asserted-by":"crossref","unstructured":"Indyk, P., Price, E., Woodruff, D.P.: On the power of adaptivity in sparse recovery. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 285\u2013294 (2011)","key":"2353_CR28","DOI":"10.1109\/FOCS.2011.83"},{"doi-asserted-by":"crossref","unstructured":"Kapralov, M., Post, I., Vondr\u00e1k, J.: Online submodular welfare maximization: Greedy is optimal. In: Proceedings of the 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1216\u20131225 (2013)","key":"2353_CR29","DOI":"10.1137\/1.9781611973105.88"},{"key":"2353_CR30","first-page":"2549","volume":"80","author":"E Kazemi","year":"2018","unstructured":"Kazemi, E., Zadimoghaddam, M., Karbasi, A.: Scalable deletion-robust submodular maximization: data summarization with privacy and fairness constraints. Int. Conf. Mach. Learn. 80, 2549\u20132558 (2018)","journal-title":"Int. Conf. Mach. Learn."},{"doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137\u2013146 (2003)","key":"2353_CR31","DOI":"10.1145\/956750.956769"},{"key":"2353_CR32","first-page":"18685","volume":"34","author":"S Kothawade","year":"2021","unstructured":"Kothawade, S., Beck, N., Killamsetty, K., Iyer, R.: Similar: submodular information measures based active learning in realistic scenarios. Adv. Neural Inf. Process. Syst. 34, 18685\u201318697 (2021)","journal-title":"Adv. Neural Inf. Process. Syst."},{"unstructured":"Krause, A., Guestrin, C.: Near-optimal nonmyopic value of information in graphical models. arXiv:1207.1394 (2012)","key":"2353_CR33"},{"key":"2353_CR34","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., Singh, A.P., Guestrin, C.: Near-optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235\u2013284 (2008)","journal-title":"J. Mach. Learn. Res."},{"key":"2353_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2809814","volume":"2","author":"R Kumar","year":"2015","unstructured":"Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in mapreduce and streaming. ACM Trans. Parallel Comput. 2, 1\u201322 (2015)","journal-title":"ACM Trans. Parallel Comput."},{"unstructured":"Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (HLT), vol. 1, pp. 510\u2013520 (2011)","key":"2353_CR36"},{"key":"2353_CR37","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ress.2018.11.010","volume":"183","author":"C Malings","year":"2019","unstructured":"Malings, C., Pozzi, M.: Submodularity issues in value-of-information-based sensor placement. Reliab. Eng. Syst. Saf. 183, 93\u2013103 (2019)","journal-title":"Reliab. Eng. Syst. Saf."},{"key":"2353_CR38","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/BFb0006528","volume":"7","author":"M Minoux","year":"1978","unstructured":"Minoux, M.: Accelerated greedy algorithms for maximizing submodular set functions. Optim. Tech. 7, 234\u2013243 (1978)","journal-title":"Optim. Tech."},{"doi-asserted-by":"crossref","unstructured":"Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondr\u00e1k, J., Krause, A.: Lazier than lazy greedy. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 29, pp. 1812\u20131818 (2015)","key":"2353_CR39","DOI":"10.1609\/aaai.v29i1.9486"},{"key":"2353_CR40","first-page":"2049","volume":"26","author":"B Mirzasoleiman","year":"2013","unstructured":"Mirzasoleiman, B., Karbasi, A., Sarkar, R., Krause, A.: Distributed submodular maximization: identifying representative elements in massive data. Adv. Neural Inf. Process. Syst. 26, 2049\u20132057 (2013)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"2353_CR41","first-page":"2449","volume":"70","author":"B Mirzasoleiman","year":"2017","unstructured":"Mirzasoleiman, B., Karbasi, A., Krause, A.: Deletion-robust submodular maximization: data summarization with the right to be forgotten. Int. Conf. Mach. Learn. 70, 2449\u20132458 (2017)","journal-title":"Int. Conf. Mach. Learn."},{"key":"2353_CR42","first-page":"4557","volume":"30","author":"S Mitrovic","year":"2017","unstructured":"Mitrovic, S., Bogunovic, I., Norouzi-Fard, A., Tarnawski, J.M., Cevher, V.: Streaming robust submodular maximization: a partitioned thresholding approach. Adv. Neural Inf. Process. Syst. 30, 4557\u20134566 (2017)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"2353_CR43","first-page":"2574","volume":"70","author":"H Namkoong","year":"2017","unstructured":"Namkoong, H., Sinha, A., Yadlowsky, S., Duchi, J.C.: Adaptive sampling probabilities for non-smooth optimization. Int. Conf. Mach. Learn. 70, 2574\u20132583 (2017)","journal-title":"Int. Conf. Mach. Learn."},{"key":"2353_CR44","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3, 177\u2013188 (1978)","journal-title":"Math. Oper. Res."},{"key":"2353_CR45","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions-I. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"1","key":"2353_CR46","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/0222016","volume":"22","author":"N Nisan","year":"1993","unstructured":"Nisan, N., Widgerson, A.: Rounds in communication complexity revisited. SIAM J. Comput. 22(1), 211\u2013219 (1993)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Salha, G., Tziortziotis, N., Vazirgiannis, M.: Adaptive submodular influence maximization with myopic feedback. In: 2018 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pp. 455\u2013462 (2018)","key":"2353_CR47","DOI":"10.1109\/ASONAM.2018.8508254"},{"unstructured":"Soma, T., Kakimura, N., Inaba, K., Kawarabayashi, K.: Optimal budget allocation: theoretical guarantee and efficient algorithm. In: Proceedings of the 31st International Conference on Machine Learning (PMLR), vol. 32, pp. 351\u2013359 (2014)","key":"2353_CR48"},{"key":"2353_CR49","first-page":"847","volume":"28","author":"T Soma","year":"2015","unstructured":"Soma, T., Yoshida, Y.: A generalization of submodular cover via the diminishing return property on the integer lattice. Adv. Neural Inf. Process. Syst. 28, 847\u2013855 (2015)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"2353_CR50","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.: Maximizing monotone submodular functions over the integer lattice. Math. Program. 172, 539\u2013563 (2018)","journal-title":"Math. Program."},{"key":"2353_CR51","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.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32, 41\u201343 (2004)","journal-title":"Oper. Res. Lett."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02353-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-023-02353-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-023-02353-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,21]],"date-time":"2024-01-21T08:03:01Z","timestamp":1705824181000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-023-02353-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,18]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["2353"],"URL":"https:\/\/doi.org\/10.1007\/s10957-023-02353-7","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2023,12,18]]},"assertion":[{"value":"26 August 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 December 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}