{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T21:52:21Z","timestamp":1770673941959,"version":"3.49.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T00:00:00Z","timestamp":1765756800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T00:00:00Z","timestamp":1765756800000},"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":["12471306"],"award-info":[{"award-number":["12471306"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2026,1]]},"DOI":"10.1007\/s10898-025-01576-4","type":"journal-article","created":{"date-parts":[[2025,12,15]],"date-time":"2025-12-15T05:32:40Z","timestamp":1765776760000},"page":"265-289","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Monotone submodular maximization under the pairwise capacity constraint"],"prefix":"10.1007","volume":"94","author":[{"given":"Yuanyuan","family":"Qiang","sequence":"first","affiliation":[]},{"given":"Bin","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,12,15]]},"reference":[{"issue":"6","key":"1576_CR1","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM"},{"issue":"4","key":"1576_CR2","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"2\u2014-3","key":"1576_CR3","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0166-218X(99)00103-1","volume":"93","author":"AA Ageev","year":"1999","unstructured":"Ageev, A.A., Sviridenko, M.: An 0.828-approximation algorithm for the uncapacitated facility location problem. Discrete Appl. Math. 93(2\u2014-3), 149\u2013156 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"1576_CR4","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/s10898-015-0394-0","volume":"67","author":"Y Xu","year":"2017","unstructured":"Xu, Y., Xu, D., Du, D., Wu, C.: Local search algorithm for universal facility location problem with linear penalties. J. Glob. Optim. 67(1), 367\u2013378 (2017)","journal-title":"J. Glob. Optim."},{"key":"1576_CR5","doi-asserted-by":"crossref","unstructured":"Bao, W., Hang, J., Zhang, M.: Submodular feature selection for partial label learning. Paper presented at the 28th International Conference on Knowledge Discovery and Data Mining, Washington, D.C., USA, 26\u201334 August (2022)","DOI":"10.1145\/3534678.3539292"},{"key":"1576_CR6","doi-asserted-by":"crossref","unstructured":"Fahrbach, M., Mirrokni, V., Zadimoghaddam, M.: Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. Paper presented at the 36th International Conference on Machine Learning, Long Beach, California, USA, 9150\u20139171 June (2019)","DOI":"10.1137\/1.9781611975482.17"},{"key":"1576_CR7","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. Paper presented at the 9th International Conference on Knowledge Discovery and Data Mining, Washington, D.C., USA, 137\u2013146 August (2003)","DOI":"10.1145\/956750.956769"},{"issue":"5","key":"1576_CR8","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/130929205","volume":"44","author":"N Buchbinder","year":"2015","unstructured":"Buchbinder, N., Feldman, M., Seffi, J., Schwartz, R.: A tight linear time ($$1\/2$$)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5), 1384\u20131402 (2015)","journal-title":"SIAM J. Comput."},{"key":"1576_CR9","doi-asserted-by":"crossref","unstructured":"Hara, J., Ono, S., Higashi, H., Tanaka, Y.: Sensor placement problem on networks for sensors with multiple specifications. Paper presented at the 32nd European Signal Processing Conference, Lyon, France, 2327\u20132331 August (2024)","DOI":"10.23919\/EUSIPCO63174.2024.10715270"},{"key":"1576_CR10","doi-asserted-by":"crossref","unstructured":"Slijepcevic, S., Potkonjak, M.: Power efficient organization of wireless sensor networks. Paper presented at the IEEE International Conference on Communications, Helsinki, Finland, 472\u2013476 June (2001)","DOI":"10.1109\/ICC.2001.936985"},{"key":"1576_CR11","doi-asserted-by":"crossref","unstructured":"Huang, C.F., Tseng, Y.C.: The coverage problem in a wireless sensor network. Paper presented at the 2nd ACM International Conference on Wireless sensor networks and applications, California, USA, 115\u2013121 September (2003)","DOI":"10.1145\/941350.941367"},{"key":"1576_CR12","unstructured":"Krause, A., Rajagopal, R., Gupta, A., Guestrin, C.: Simultaneous placement and scheduling of sensors. Paper presented at the 8th ACM\/IEEE International Conference on Information Processing in Sensor Networks, San Francisco, USA, 181\u2013192 April (2009)"},{"key":"1576_CR13","doi-asserted-by":"crossref","unstructured":"Zhu, Q., Wang, R., Chen, Q., Liu, Y., Qin, W.: Iot gateway: Bridging wireless sensor networks into internet of things. Paper presented at the 8th IEEE\/IFIP International Conference on Embedded and Ubiquitous Computing, Hong Kong, China, 347\u2013352, December (2010)","DOI":"10.1109\/EUC.2010.58"},{"key":"1576_CR14","doi-asserted-by":"crossref","unstructured":"Aazam, M., Hung, P.P., Huh, E.N.: Smart gateway based communication for cloud of things. Paper prensented at the 9th International Conference on Intelligent Sensors, Sensor Networks and Information Processing, Singapore, 1\u20136, April (2014)","DOI":"10.1109\/ISSNIP.2014.6827673"},{"issue":"2","key":"1576_CR15","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1287\/ijoc.2022.0384","volume":"36","author":"S Tang","year":"2024","unstructured":"Tang, S., Yuan, J.: Group equality in adaptive submodular maximization. INFORMS J. Comput. 36(2), 359\u2013376 (2024)","journal-title":"INFORMS J. Comput."},{"key":"1576_CR16","unstructured":"Haba, R., Kazemi, E., Feldman, M., Karbasi, A.: Streaming submodular maximization under a k-set system constraint. Paper presented at the 37th International Conference on Machine Learning, virtual, 3939\u20133949 May (2020)"},{"key":"1576_CR17","doi-asserted-by":"crossref","unstructured":"Nong, Q.Q., Wang, Y., Gong, S.N.: A semi-streaming algorithm for monotone regularized submodular maximization with a matroid constraint. J. Oper. Res. Soc. China 0(0), 1\u201317 (2024)","DOI":"10.1007\/s40305-023-00525-w"},{"key":"1576_CR18","unstructured":"Feldman, M., Liu, P., Norouzi-Fard, A., Svensson, O., Zenklusen, R.: Streaming submodular maximization under matroid constraints. Paper presented at the 49th EATCS International Colloquium on Automata, Languages and Programming, Paris, France, 59:1\u201359:20 July (2022)"},{"issue":"3","key":"1576_CR19","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"LA Wolsey","year":"1982","unstructured":"Wolsey, L.A.: Maximising real-valued submodular functions: primal and dual heuristics for location problems. Math. Oper. Res. 7(3), 410\u2013425 (1982)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1576_CR20","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(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"1576_CR21","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/3543516.3453922","volume":"49","author":"K Han","year":"2021","unstructured":"Han, K., Cui, S., Zhu, T., Zhang, E., Wu, B., Yin, Z., Xu, T., Tang, S., Huang, H.: Approximation algorithms for submodular data summarization with a knapsack constraint. ACM SIGMETRICS Perform. Eval. Rev. 49(1), 65\u201366 (2021)","journal-title":"ACM SIGMETRICS Perform. Eval. Rev."},{"key":"1576_CR22","doi-asserted-by":"crossref","unstructured":"Pham, C.V., Tran, T.D., Ha, D.T.K., Thai, M.T.: Linear query approximation algorithms for non-monotone submodular maximization under knapsack constraint. Paper presented at the 32nd International Joint Conference on Artificial Intelligence, Macao, S.A.R, 4127\u20134135 August (2023)","DOI":"10.24963\/ijcai.2023\/459"},{"issue":"1","key":"1576_CR23","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/3606376.3593573","volume":"51","author":"S Cui","year":"2023","unstructured":"Cui, S., Han, K., Tang, J., Huang, H., Li, X., Li, Z.: Streaming algorithms for constrained submodular maximization. ACM SIGMETRICS Perform. Eval. Rev. 51(1), 65\u201366 (2023)","journal-title":"ACM SIGMETRICS Perform. Eval. Rev."},{"issue":"4","key":"1576_CR24","doi-asserted-by":"publisher","first-page":"729","DOI":"10.1287\/moor.2013.0592","volume":"38","author":"A Kulik","year":"2013","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Approximations for monotone and non-monotone submodular maximization with knapsack constraints. Math. Oper. Res. 38(4), 729\u2013739 (2013)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"1576_CR25","doi-asserted-by":"publisher","first-page":"53736","DOI":"10.1109\/ACCESS.2018.2871668","volume":"6","author":"Q Yu","year":"2018","unstructured":"Yu, Q., Xu, L., Cui, S.: Streaming algorithms for news and scientific literature recommendation: monotone submodular maximization with a $$d$$-knapsack constraint. IEEE Access 6(1), 53736\u201353747 (2018)","journal-title":"IEEE Access"},{"issue":"7","key":"1576_CR26","doi-asserted-by":"publisher","first-page":"1327","DOI":"10.1109\/TKDE.2018.2854182","volume":"31","author":"Y Wang","year":"2018","unstructured":"Wang, Y., Li, Y., Tan, K.L.: Efficient representative subset selection over sliding windows. IEEE Trans. Knowl. Data Eng. 31(7), 1327\u20131340 (2018)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"1576_CR27","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Constrained submodular maximization via new bounds for DR-submodular functions. Paper presented at the 56th Annual ACM Symposium on Theory of Computing, Vancouver, Canada, 1820\u20131831 June (2024)","DOI":"10.1145\/3618260.3649630"},{"issue":"1","key":"1576_CR28","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. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"6","key":"1576_CR29","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., Pal, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131746 (2011)","journal-title":"SIAM J. Comput."},{"key":"1576_CR30","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Deterministic algorithm and faster algorithm for submodular maximization subject to a matroid constraint. Paper presented at the 65th IEEE Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 700\u2013712 October (2024)","DOI":"10.1109\/FOCS61266.2024.00050"},{"key":"1576_CR31","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Baharan, M., Karbasi, A., Krause, A.: Streaming submodular maximization: massive data summarization on the fly. Paper presented at the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, New York, NY, USA, 671\u2013680 August (2014)","DOI":"10.1145\/2623330.2623637"},{"issue":"4","key":"1576_CR32","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/3588564","volume":"70","author":"M Feldman","year":"2023","unstructured":"Feldman, M., Norouzi-Fard, A., Svensson, O., Zenklusen, R.: The one-way communication complexity of submodular maximization with applications to streaming and robustness. J. ACM 70(4), 24\u201312452 (2023)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"1576_CR33","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.: Submodular maximization meets streaming: Matchings, matroids, and more. Math. Program. 154(1\u20132), 225\u2013247 (2015)","journal-title":"Math. Program."},{"key":"1576_CR34","doi-asserted-by":"crossref","unstructured":"Oveis Gharan, S., Vondr\u00e1k, J.: Submodular Maximization by Simulated Annealing. Paper presented at the 22nd Annual Symposium on Discrete Algorithms, San Francisco, California, USA, 1098\u20131116 January (2011)","DOI":"10.1137\/1.9781611973082.83"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01576-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-025-01576-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-025-01576-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T04:00:27Z","timestamp":1770609627000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-025-01576-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,15]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["1576"],"URL":"https:\/\/doi.org\/10.1007\/s10898-025-01576-4","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,15]]},"assertion":[{"value":"26 June 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 November 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}]}}