{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,17]],"date-time":"2026-05-17T04:57:21Z","timestamp":1778993841913,"version":"3.51.4"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,4,18]],"date-time":"2022-04-18T00:00:00Z","timestamp":1650240000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,4,18]],"date-time":"2022-04-18T00:00:00Z","timestamp":1650240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s10878-022-00858-x","type":"journal-article","created":{"date-parts":[[2022,4,18]],"date-time":"2022-04-18T03:30:03Z","timestamp":1650252603000},"page":"723-751","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Maximizing k-submodular functions under budget constraint: applications and streaming algorithms"],"prefix":"10.1007","volume":"44","author":[{"given":"Canh V.","family":"Pham","sequence":"first","affiliation":[]},{"given":"Quang C.","family":"Vu","sequence":"additional","affiliation":[]},{"given":"Dung K. T.","family":"Ha","sequence":"additional","affiliation":[]},{"given":"Tai T.","family":"Nguyen","sequence":"additional","affiliation":[]},{"given":"Nguyen D.","family":"Le","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,4,18]]},"reference":[{"key":"858_CR1","doi-asserted-by":"publisher","unstructured":"Badanidiyuru A, Vondr\u00e1k J (2014) Fast algorithms for maximizing submodular functions. In: Chekuri C (ed) Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, SIAM, pp 1497\u20131514. https:\/\/doi.org\/10.1137\/1.9781611973402.110","DOI":"10.1137\/1.9781611973402.110"},{"key":"858_CR2","doi-asserted-by":"crossref","unstructured":"Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: massive data summarization on the fly. In: Macskassy SA, Perlich C, Leskovec J, Wang W, Ghani R (eds) The 20th ACM SIGKDD international conference on knowledge discovery and data mining, KDD \u201914, New York, NY, USA\u2014August 24\u201327, 2014, ACM, pp 671\u2013680","DOI":"10.1145\/2623330.2623637"},{"key":"858_CR3","unstructured":"Bodik P, Hong W, Guestrin C, Madden S, Paskin M, Thibaux R (2004) Intel lab. http:\/\/db.csail.mit.edu\/labdata\/labdata.html"},{"key":"858_CR4","doi-asserted-by":"crossref","unstructured":"Borgs C, Brautbar M, Chayes JT, Lucier B (2014) Maximizing social influence in nearly optimal time. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, Oregon, USA, January 5\u20137, 2014, pp 946\u2013957","DOI":"10.1137\/1.9781611973402.70"},{"issue":"5","key":"858_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 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"},{"issue":"6","key":"858_CR6","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"},{"issue":"1\u20132","key":"858_CR7","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/s10107-015-0900-7","volume":"154","author":"A Chakrabarti","year":"2015","unstructured":"Chakrabarti A, Kale S (2015) Submodular maximization meets streaming: matchings, matroids, and more. Math Program 154(1\u20132):225\u2013247","journal-title":"Math Program"},{"key":"858_CR8","doi-asserted-by":"crossref","unstructured":"Chen W, Yuan Y, Zhang L (2010) Scalable influence maximization in social networks under the linear threshold model. In: ICDM 2010, The 10th IEEE international conference on data mining, Sydney, Australia, 14\u201317 December 2010, pp 88\u201397","DOI":"10.1109\/ICDM.2010.118"},{"key":"858_CR9","unstructured":"Gomes R, Krause A (2010) Budgeted nonparametric learning from data streams. In: F\u00fcrnkranz J, Joachims T (eds) Proceedings of the 27th international conference on machine learning (ICML-10), June 21\u201324, 2010, Haifa, Israel, Omnipress, pp 391\u2013398"},{"key":"858_CR10","unstructured":"Haba R, Kazemi E, Feldman M, Karbasi A (2020) Streaming submodular maximization under a k-set system constraint. In: Proceedings of the 37th international conference on machine learning, ICML 2020, 2020, virtual event, PMLR, proceedings of machine learning research, vol 119, pp 3939\u20133949"},{"issue":"4","key":"858_CR11","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1007\/s00453-019-00628-y","volume":"82","author":"C Huang","year":"2020","unstructured":"Huang C, Kakimura N, Yoshida Y (2020) Streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica 82(4):1006\u20131032","journal-title":"Algorithmica"},{"key":"#cr-split#-858_CR12.1","doi-asserted-by":"crossref","unstructured":"Iwata S, Tanigawa S, Yoshida Y (2016) Improved approximation algorithms for k-submodular function maximization. In: Krauthgamer R","DOI":"10.1137\/1.9781611974331.ch30"},{"key":"#cr-split#-858_CR12.2","unstructured":"(ed) Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, SODA 2016, Arlington, VA, USA, 2016, SIAM, pp 404-413"},{"key":"858_CR13","doi-asserted-by":"publisher","unstructured":"Kempe D, Kleinberg JM, Tardos \u00c9 (2003) Maximizing the spread of influence through a social network. In: Proceedings of the ninth ACM SIGKDD international conference on knowledge discovery and data mining, Washington, DC, USA, August 24\u201327, 2003, pp 137\u2013146. https:\/\/doi.org\/10.1145\/956750.956769","DOI":"10.1145\/956750.956769"},{"key":"858_CR14","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause A, Singh AP, Guestrin C (2008) Near-optimal sensor placements in gaussian processes: theory, efficient algorithms and empirical studies. J Mach Learn Res 9:235\u2013284","journal-title":"J Mach Learn Res"},{"key":"858_CR15","doi-asserted-by":"crossref","unstructured":"Kumar R, Moseley B, Vassilvitskii S, Vattani A (2013) Fast greedy algorithms in mapreduce and streaming. In: Blelloch GE, V\u00f6cking B (eds) 25th ACM symposium on parallelism in algorithms and architectures, SPAA \u201913, Montreal, QC, Canada\u201423\u201325, 2013, ACM, pp 1\u201310","DOI":"10.1145\/2486159.2486168"},{"key":"858_CR16","unstructured":"Leskovec J, Krevl (2014) A. snap datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"issue":"2","key":"858_CR17","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1109\/TNET.2019.2898413","volume":"27","author":"X Li","year":"2019","unstructured":"Li X, Smith JD, Dinh TN, Thai MT (2019) Tiptop: (almost) exact solutions for influence maximization in billion-scale networks. IEEE\/ACM Trans Netw 27(2):649\u2013661","journal-title":"IEEE\/ACM Trans Netw"},{"key":"858_CR18","doi-asserted-by":"crossref","unstructured":"Mirzasoleiman B, Badanidiyuru A, Karbasi A, Vondr\u00e1k J, Krause A (2015) Lazier than lazy greedy. In: Bonet B, Koenig S (eds) Proceedings of the twenty-ninth AAAI conference on artificial intelligence, 2015, Austin, Texas, USA, AAAI Press, pp 1812\u20131818","DOI":"10.1609\/aaai.v29i1.9486"},{"key":"858_CR19","unstructured":"Mirzasoleiman B, Badanidiyuru A, Karbasi A (2016) Fast constrained submodular maximization: personalized data summarization. In: Balcan M, Weinberger KQ (eds) Proceedings of the 33nd international conference on machine learning, ICML 2016, New York City, NY, USA, June 19\u201324, 2016, JMLR.org, JMLR workshop and conference proceedings, vol\u00a048, pp 1358\u20131367"},{"issue":"1","key":"858_CR20","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. https:\/\/doi.org\/10.1007\/BF01588971","journal-title":"Math Program"},{"issue":"6","key":"858_CR21","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1109\/JSAC.2013.130610","volume":"31","author":"H Nguyen","year":"2013","unstructured":"Nguyen H, Zheng R (2013) On budgeted influence maximization in social networks. IEEE J Sel Areas Commun 31(6):1084\u20131094. https:\/\/doi.org\/10.1109\/JSAC.2013.130610","journal-title":"IEEE J Sel Areas Commun"},{"key":"858_CR22","unstructured":"Nguyen L, Thai M (2020) Streaming k-submodular maximization under noise subject to size constraint. In: Daum\u00e9 H, Singh A (eds) Proceedings of the international conference on machine learning, (ICML-2020), thirty-seventh international conference on machine learning"},{"key":"858_CR23","unstructured":"Ohsaka N, Yoshida Y (2015) Monotone k-submodular function maximization with size constraints. In: Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R (eds) Advances in neural information processing systems 28: annual conference on neural information processing systems 2015, Montreal, Quebec, Canada, pp 694\u2013702"},{"key":"858_CR24","doi-asserted-by":"crossref","unstructured":"Oshima H (2017) Derandomization for k-submodular maximization. In: Brankovic L, Ryan J, Smyth WF (eds) Combinatorial algorithms\u201428th international workshop, IWOCA 2017, Lecture notes in computer science, vol 10765, pp 88\u201399","DOI":"10.1007\/978-3-319-78825-8_8"},{"issue":"4","key":"858_CR25","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1109\/TEVC.2017.2749263","volume":"22","author":"C Qian","year":"2018","unstructured":"Qian C, Shi J, Tang K, Zhou Z (2018) Constrained monotone k-submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee. IEEE Trans Evol Comput 22(4):595\u2013608","journal-title":"IEEE Trans Evol Comput"},{"key":"858_CR26","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, ICML 2020, 13\u201318, 2020, virtual event, proceedings of machine learning research, vol 119, pp 7887\u20137897"},{"key":"858_CR27","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, ICML 2020, 13-18 July 2020, virtual event, PMLR, proceedings of machine learning research, vol 119, pp 7887\u20137897"},{"key":"858_CR28","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 Optim 23:105\u2013113","journal-title":"Discret Optim"},{"key":"858_CR29","volume-title":"Combinatorial optimization: polyhedra and efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. Springer, Algorithms and Combinatorics"},{"key":"858_CR30","unstructured":"Singh AP, Guillory A, Bilmes JA (2012) On bisubmodular maximization. In: Lawrence ND, Girolami MA (eds) Proceedings of the fifteenth international conference on artificial intelligence and statistics, AISTATS 2012, La Palma, Canary Islands, Spain, 21\u201323, 2012, JMLR.org, JMLR proceedings, vol\u00a022, pp 1055\u20131063"},{"key":"858_CR31","unstructured":"Soma T (2019) No-regret algorithms for online $$k$$-submodular maximization. In: Chaudhuri K, Sugiyama M (eds) The 22nd international conference on artificial intelligence and statistics, AISTATS 2019, 16\u201318 April 2019, Naha, Okinawa, Japan, proceedings of machine learning research, vol\u00a089, pp 1205\u20131214"},{"issue":"1","key":"858_CR32","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. Oper Res Lett 32(1):41\u201343","journal-title":"Oper Res Lett"},{"issue":"1","key":"858_CR33","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.orl.2021.11.010","volume":"50","author":"Z Tang","year":"2022","unstructured":"Tang Z, Wang C, Chan H (2022) On maximizing a monotone k-submodular function under a knapsack constraint. Oper Res Lett 50(1):28\u201331","journal-title":"Oper Res Lett"},{"key":"858_CR34","doi-asserted-by":"crossref","unstructured":"Thapper J, Zivn\u00fd S (2012) The power of linear programming for valued csps. In: 53rd annual IEEE symposium on foundations of computer science, FOCS 2012, New Brunswick, NJ, USA, 2012, IEEE Computer Society, pp 669\u2013678","DOI":"10.1109\/FOCS.2012.25"},{"key":"858_CR35","unstructured":"Wang B, Zhou H (2021) Multilinear extension of k-submodular functions. CoRR abs\/2107.07103, https:\/\/arxiv.org\/abs\/2107.07103, eprint2107.07103"},{"key":"#cr-split#-858_CR36.1","doi-asserted-by":"crossref","unstructured":"Ward J, Zivn\u00fd S (2014) Maximizing bisubmodular and k-submodular functions. In: Chekuri C","DOI":"10.1137\/1.9781611973402.108"},{"key":"#cr-split#-858_CR36.2","unstructured":"(ed) Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, Oregon, USA, 2014, SIAM, pp 1468-1481"},{"issue":"3","key":"858_CR37","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"LA Wolsey","year":"1982","unstructured":"Wolsey LA (1982) Maximising real-valued submodular functions: primal and dual heuristics for location problems. Math Oper Res 7(3):410\u2013425","journal-title":"Math Oper Res"},{"key":"858_CR38","doi-asserted-by":"crossref","unstructured":"Yang R, Xu D, Cheng Y, Gao C, Du D (2019) Streaming submodular maximization under noises. In: 39th IEEE international conference on distributed computing systems, ICDCS 2019, Dallas, TX, USA, July 7\u201310, 2019, IEEE, pp 348\u2013357","DOI":"10.1109\/ICDCS.2019.00042"},{"key":"858_CR39","doi-asserted-by":"crossref","unstructured":"Yu Q, Xu EL, Cui S (2016) Submodular maximization with multi-knapsack constraints and its applications in scientific literature recommendations. In: 2016 IEEE global conference on signal and information processing, GlobalSIP 2016, Washington, DC, USA, 2016, IEEE, pp 1295\u20131299","DOI":"10.1109\/GlobalSIP.2016.7906050"},{"key":"858_CR40","doi-asserted-by":"crossref","unstructured":"Zhang Y, Li M, Yang D, Xue G (2019) A budget feasible mechanism for k-topic influence maximization in social networks. In: 2019 IEEE global communications conference, GLOBECOM 2019, Waikoloa, HI, USA, December 9\u201313, 2019, IEEE, pp 1\u20136","DOI":"10.1109\/GLOBECOM38437.2019.9013859"},{"key":"858_CR41","doi-asserted-by":"crossref","unstructured":"Zheng L, Chan H, Loukides G, Li M (2021) Maximizing approximately k-submodular functions. In: Demeniconi C, Davidson I (eds) Proceedings of the 2021 SIAM international conference on data mining, SDM 2021, Virtual Event, 2021, SIAM, pp 414\u2013422","DOI":"10.1137\/1.9781611976700.47"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00858-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00858-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00858-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,29]],"date-time":"2022-07-29T07:33:14Z","timestamp":1659079994000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00858-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,18]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["858"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00858-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,18]]},"assertion":[{"value":"21 March 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}