{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T03:48:28Z","timestamp":1777002508948,"version":"3.51.4"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T00:00:00Z","timestamp":1733270400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T00:00:00Z","timestamp":1733270400000},"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":["12301419"],"award-info":[{"award-number":["12301419"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100014718","name":"Innovative Research Group Project of the National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11991022"],"award-info":[{"award-number":["11991022"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012165","name":"Key Technologies Research and Development Program","doi-asserted-by":"publisher","award":["2021YFA1000403"],"award-info":[{"award-number":["2021YFA1000403"]}],"id":[{"id":"10.13039\/501100012165","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":[[2025,1]]},"DOI":"10.1007\/s10878-024-01240-9","type":"journal-article","created":{"date-parts":[[2024,12,4]],"date-time":"2024-12-04T19:29:35Z","timestamp":1733340575000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Greedy algorithms for stochastic monotone k-submodular maximization under full-bandit feedback"],"prefix":"10.1007","volume":"49","author":[{"given":"Xin","family":"Sun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tiande","family":"Guo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Congying","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongyang","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,4]]},"reference":[{"issue":"1","key":"1240_CR1","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0097539701398375","volume":"32","author":"P Auer","year":"2002","unstructured":"Auer P, Cesa-Bianchi N, Freund Y, Schapire RE (2002) The nonstochastic multiarmed bandit problem. SIAM J Comput 32(1):48\u201377","journal-title":"SIAM J Comput"},{"key":"1240_CR2","doi-asserted-by":"crossref","unstructured":"Balkanski E, Rubinstein A, Singer Y (2019a) An exponential speedup in parallel running time for submodular maximization without loss in approximation. In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms, pp 283-302","DOI":"10.1137\/1.9781611975482.19"},{"key":"1240_CR3","doi-asserted-by":"crossref","unstructured":"Balkanski E, Rubinstein A, Singer Y (2019b) An optimal approximation for submodular maximization under a matroid constraint in the adaptive complexity model. In Proceedings of the 51st ACM SIGACT Symposium on Theory of Computing, pp 66-77","DOI":"10.1145\/3313276.3316304"},{"issue":"3","key":"1240_CR4","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 Oper Res 44(3):988\u20131005","journal-title":"Math Oper Res"},{"issue":"6","key":"1240_CR5","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G C\u0103linescu","year":"2011","unstructured":"C\u0103linescu G, Chekuri C, P\u00e1l M, Vondr\u00e1k J (2011) Maximizing a monotone submodular function subject to a matroid constraint. SIAM J Comput 40(6):1740\u20131766","journal-title":"SIAM J Comput"},{"key":"1240_CR6","doi-asserted-by":"crossref","unstructured":"Chaturvedi A, Nguyen HL, Zakynthinou L (2021) Differentially private decomposable submodular maximization. In Proceedings of the 46th AAAI Conference on Artificial Intelligence, pp 6984-6992","DOI":"10.1609\/aaai.v35i8.16860"},{"issue":"3","key":"1240_CR7","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/S0097539700382820","volume":"35","author":"C Chekuri","year":"2005","unstructured":"Chekuri C, Khanna S (2005) A polynomial time approximation scheme for the multiple knapsack problem. SIAM J Comput 35(3):713\u2013728","journal-title":"SIAM J Comput"},{"key":"1240_CR8","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2021.3103386","author":"W Chen","year":"2021","unstructured":"Chen W, Ishibuchi H, Shang K (2021) Fast greedy subset selection from large candidate solution sets in evolutionary multi-objective optimization. IEEE Trans Evolut Comput. https:\/\/doi.org\/10.1109\/TEVC.2021.3103386","journal-title":"IEEE Trans Evolut Comput"},{"key":"1240_CR9","unstructured":"Ene A, Nguyen HL (2022) Streaming algorithm for monotone $$k$$-submodular maximization with cardinality constraints. In: Proceedings of the 39th International Conference on Machine Learning, pp 5944-5967"},{"issue":"4","key":"1240_CR10","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. J ACM 45(4):634\u2013652","journal-title":"J ACM"},{"issue":"3","key":"1240_CR11","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00453-020-00757-9","volume":"83","author":"M Feldman","year":"2021","unstructured":"Feldman M (2021) Guess free maximization of submodular and linear sums. Algorithmica 83(3):853\u2013878","journal-title":"Algorithmica"},{"key":"1240_CR12","doi-asserted-by":"crossref","unstructured":"Feldman M, Naor J, Schwartz R (2011) A unified continuous greedy algorithm for submodular maximization. In: Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, pp 570-579","DOI":"10.1109\/FOCS.2011.46"},{"issue":"2","key":"1240_CR13","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/130920277","volume":"43","author":"Y Filmus","year":"2014","unstructured":"Filmus Y, Ward J (2014) Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J Comput 43(2):514\u2013542","journal-title":"SIAM J Comput"},{"key":"1240_CR14","unstructured":"Fourati F, Aggarwal V, Quinn CJ, Alouini MS (2023) Randomized greedy learning for non-monotone stochastic submodular maximization under full-bandit feedback In: Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, PMLR 206: pp 7455-7471"},{"key":"1240_CR15","doi-asserted-by":"crossref","unstructured":"Gharan SO, Vondr\u00e1k J (2011) Submodular maximization by simulated annealing. In: Proceedings of the 22 Annual ACM-SIAM Symposium on Discrete Algorithms, pp 1098-1116","DOI":"10.1137\/1.9781611973082.83"},{"issue":"6","key":"1240_CR16","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans MX, Williamson DP (1995) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J ACM 42(6):1115\u20131145","journal-title":"J ACM"},{"key":"1240_CR17","doi-asserted-by":"crossref","unstructured":"Gridchyn I, Kolmogorov V (2013) Potts model, parametric maxflow and $$k$$-submodular functions. In: Proceedings of the 14th IEEE International Conference on Computer Vision, pp 2320-2327","DOI":"10.1109\/ICCV.2013.288"},{"key":"1240_CR18","doi-asserted-by":"crossref","unstructured":"Gupta A, Ligett K, McSherry G, Roth A, Talwar K (2010) Differentially private combinatorial optimization. In: Proceedings of the 21st ACM Symposium on Discrete Algorithms, pp 1106-1125","DOI":"10.1137\/1.9781611973075.90"},{"issue":"301","key":"1240_CR19","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding W (1963) Probability inequalities for sums of bounded random variables. J Am Stat Assoc 58(301):13\u201330","journal-title":"J Am Stat Assoc"},{"key":"1240_CR20","doi-asserted-by":"crossref","unstructured":"Huber A, Kolmogorov V (2012) Towards minimizing $$k$$-submodular functions. In: Proceedings of the 2nd International Symposium on Combinatorial Optimization, pp 451-462","DOI":"10.1007\/978-3-642-32147-4_40"},{"key":"1240_CR21","doi-asserted-by":"crossref","unstructured":"Iwata S, Tanigawa S, Yoshida Y (2016) Improved approximation algorithms for $$k$$-submodular function maximization. In: Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms, pp 404-413","DOI":"10.1137\/1.9781611974331.ch30"},{"key":"1240_CR22","doi-asserted-by":"crossref","unstructured":"Li W, Vondr\u00e1k J (2021) Estimating the Nash social welfare for coverage and other submodular valuations. In: Proceedings of the 32nd Annual ACM Symposium on Discrete Algorithms, pp 1119-1130","DOI":"10.1137\/1.9781611976465.69"},{"key":"1240_CR23","unstructured":"Lu C, Yang W, Gao S. (2024) Regularized non-monotone submodular maximization. Preprint arXiv:2103.10008"},{"issue":"3","key":"1240_CR24","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"},{"issue":"1","key":"1240_CR25","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 Progr 14(1):265\u2013294","journal-title":"Math Progr"},{"issue":"7","key":"1240_CR26","doi-asserted-by":"publisher","first-page":"3797","DOI":"10.1287\/mnsc.2022.4558","volume":"69","author":"R Niazadeh","year":"2020","unstructured":"Niazadeh R, Golrezaei N, Wang J, Susan F, Badanidiyuru A (2020) Online learning via offline greedy: applications in market design and optimization. Manag Sci 69(7):3797\u20133817","journal-title":"Manag Sci"},{"key":"1240_CR27","unstructured":"Nie G, Agarwal M, Umrawal AK, Aggarwal V, Quinn CJ (2022) An explore-then-commit algorithm for submodular maximization under full-bandit feedback. In: Proceedings of the 38th Conference on Uncertainty in Artificial Intelligence, PMLR 180: pp 1541-1551"},{"key":"1240_CR28","unstructured":"Nie G, Zhu Y, Nadew YY, Basu S, Pavan A, Quinn CJ (2023) Size-constrained $$k$$-submodular maximization in near-linear time. In: Proceedings of the 39th Conference on Uncertainty in Artificial Intelligence, PMLR 216: pp 545-1554"},{"key":"1240_CR29","unstructured":"Ohsaka N, Yoshida Y (2015) Monotone $$k$$-submodular function maximization with size constraints. In: Proceedings of the 29th Conference on Advances in Neural Information Processing Systems, pp 694-702"},{"key":"1240_CR30","unstructured":"Qi B (2023) On maximizing sums of non-monotone submodular and linear functions. In: Proceedings of the 33rd International Symposium on Algorithms and Computation, 41: pp 1-16"},{"key":"1240_CR31","unstructured":"Rafiey A, Yoshida Y (2020) Fast and private submodular and $$k$$-submodular functions maximization with matroid constraints. In: Proceedings of the 37th International Conference on Machine Learning, pp 7887-7897"},{"issue":"5","key":"1240_CR32","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1090\/S0002-9904-1952-09620-8","volume":"58","author":"H Robbins","year":"1952","unstructured":"Robbins H (1952) Some aspects of the sequential design of experiments. Bull Am Math Soc 58(5):527\u2013535","journal-title":"Bull Am Math Soc"},{"key":"1240_CR33","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.disopt.2017.01.003","volume":"23","author":"S Sakaue","year":"2017","unstructured":"Sakaue S (2017) On maximizing a monotone $$k$$-submodular function subject to a matroid constraint. Discret Opt 23:105\u2013113","journal-title":"Discret Opt"},{"key":"1240_CR34","unstructured":"Spaeh F, Ene A, Nguyen HL (2023) Online and streaming algorithms for constrained $$k$$-submodular maximization. arXiv preprint arXiv:2305.16013"},{"issue":"4","key":"1240_CR35","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 Oper Res 42(4):1197\u20131218","journal-title":"Math Oper Res"},{"key":"1240_CR36","doi-asserted-by":"crossref","unstructured":"Sun X, Han C, Wu C, Xu D, Zhou Y (2023) The regularized submodular maximization via the Lyapunov method. In: Proceedings of the 29th International Computing and Combinatorics Conference, accept","DOI":"10.1007\/978-3-031-49193-1_10"},{"key":"1240_CR37","doi-asserted-by":"publisher","first-page":"3212","DOI":"10.1007\/s10878-022-00875-w","volume":"44","author":"X Sun","year":"2022","unstructured":"Sun X, Li G, Zhang Y, Zhang Z (2022) Private non-monotone submodular maximization. J Comb Opt 44:3212\u20133232","journal-title":"J Comb Opt"},{"issue":"3","key":"1240_CR38","doi-asserted-by":"publisher","first-page":"2050","DOI":"10.3934\/jimo.2022031","volume":"19","author":"X Sun","year":"2023","unstructured":"Sun X, Xu D, Zhang D, Zhou Y (2023) An adaptive algorithm for maximization of non-submodular function with a matroid constraint. J Ind Manag Opt 19(3):2050\u20132070","journal-title":"J Ind Manag Opt"},{"key":"1240_CR39","unstructured":"Wan Z, Zhang J, Chen W, Sun X, Zhang Z (2023) Bandit multi-linear DR-submodular maximization and its applications on adversarial submodular bandits. In: Proceedings of the 40th International Conference on Machine Learning, PMLR 202: pp 35491-35524"},{"key":"1240_CR40","doi-asserted-by":"crossref","unstructured":"Ward J, \u017divn\u00fd S (2014) Maximizing bisubmodular and $$k$$-submodular functions. In: Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms, pp 1468-1481","DOI":"10.1137\/1.9781611973402.108"},{"key":"1240_CR41","unstructured":"Zhang M, Chen L, Hassani H, Karbasi A (2019) Online continuous submodular maximization: From full-information to bandit feedback. In: Proceedings of the 33rd Conference on Advances in Neural Information Processing Systems, pp 9206-9217"},{"key":"1240_CR42","unstructured":"Zhang Q, Deng Z, Chen Z, Zhou K, Hu H, Yang Y (2023) Online learning for non-monotone submodular maximization: From full information to bandit feedback. In: Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, PMLR 206: pp 3515-3537"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01240-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01240-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01240-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T19:04:04Z","timestamp":1737745444000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01240-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,4]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["1240"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01240-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,4]]},"assertion":[{"value":"11 November 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2024","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 declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of intrest"}}],"article-number":"7"}}