{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T14:46:15Z","timestamp":1773153975301,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,8,14]],"date-time":"2024-08-14T00:00:00Z","timestamp":1723593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,14]],"date-time":"2024-08-14T00:00:00Z","timestamp":1723593600000},"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\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12301415"],"award-info":[{"award-number":["12301415"]}],"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":[[2024,12]]},"DOI":"10.1007\/s10898-024-01406-z","type":"journal-article","created":{"date-parts":[[2024,8,14]],"date-time":"2024-08-14T02:02:00Z","timestamp":1723600920000},"page":"1007-1030","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Budget-constrained profit maximization without non-negative objective assumption in social networks"],"prefix":"10.1007","volume":"90","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":"Yue","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Dingzhu","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,8,14]]},"reference":[{"issue":"3","key":"1406_CR1","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1086\/209118","volume":"14","author":"JJ Brown","year":"1987","unstructured":"Brown, J.J., Reingen, P.H.: Social ties and word-of-mouth referral behavior. J. Consum. Res. 14(3), 350\u2013362 (1987)","journal-title":"J. Consum. Res."},{"issue":"1","key":"1406_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1177\/0049124193022001005","volume":"22","author":"M Morris","year":"1993","unstructured":"Morris, M.: Epidemiology and social networks: modeling structured diffusion. Sociol. Methods Res. 22(1), 99\u2013126 (1993)","journal-title":"Sociol. Methods Res."},{"key":"1406_CR3","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/978-3-642-17572-5_48","volume-title":"Internet and Network Economics","author":"A Borodin","year":"2010","unstructured":"Borodin, A., Filmus, Y., Oren, J.: Threshold models for competitive influence in social networks. In: Saberi, A. (ed.) Internet and Network Economics, pp. 539\u2013550. Springer, Heidelberg (2010)"},{"key":"1406_CR4","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 137\u2013146. Association for Computing Machinery (ACM), New York (2003)","DOI":"10.1145\/956750.956769"},{"key":"1406_CR5","doi-asserted-by":"crossref","unstructured":"Borgs, C., Brautbar, M., Chayes, J., Lucier, B.: Maximizing social influence in nearly optimal time. In: Proc. Annu. ACM SIAM Symp. Discrete Algorithms, pp. 946\u2013957. Association for Computing Machinery, New York (2014)","DOI":"10.1137\/1.9781611973402.70"},{"key":"1406_CR6","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1016\/j.tcs.2015.03.048","volume":"609","author":"X Chen","year":"2016","unstructured":"Chen, X., Hu, X., Wang, C.: Approximation for the minimum cost doubly resolving set problem. Theor. Comput. Sci. 609, 526\u2013543 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"1406_CR7","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-1-4419-8462-3_9","volume-title":"Social Network Data Analytics","author":"MA Hasan","year":"2011","unstructured":"Hasan, M.A., Zaki, M.J.: A survey of link prediction in social networks. In: Aggarwal, C.C. (ed.) Social Network Data Analytics, pp. 243\u2013275. Springer, Boston (2011)"},{"key":"1406_CR8","doi-asserted-by":"crossref","unstructured":"Lappas, T., Terzi, E., Gunopulos, D., Mannila, H.: Finding effectors in social networks. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 1059\u20131068. Association for Computing Machinery (ACM), New York (2010)","DOI":"10.1145\/1835804.1835937"},{"issue":"1","key":"1406_CR9","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(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"1406_CR10","doi-asserted-by":"crossref","unstructured":"Ohsaka, N., Akiba, T., Yoshida, Y., Kawarabayashi, K.: Fast and accurate influence maximization on large networks with pruned monte-carlo simulations. In: Proc. Natl. Conf. Artif. Intell., 28, pp. 138\u2013144. AAAI, California (2014)","DOI":"10.1609\/aaai.v28i1.8726"},{"key":"1406_CR11","doi-asserted-by":"crossref","unstructured":"Chen, W., Yuan, Y., Zhang, L.: Scalable influence maximization in social networks under the linear threshold model. In: Proc. IEEE Int. Conf. Data Min. ICDM, pp. 88\u201397. Institute of Electrical and Electronics Engineers Inc., New Jersey (2010)","DOI":"10.1109\/ICDM.2010.118"},{"key":"1406_CR12","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Krause, A., Guestrin, C., Faloutsos, C., Vanbriesen, J., Glance, N.: Cost-effective outbreak detection in networks. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 420\u2013429. Association for Computing Machinery, New York (2007)","DOI":"10.1145\/1281192.1281239"},{"key":"1406_CR13","doi-asserted-by":"crossref","unstructured":"Chen, W., Wang, Y., Yang, S.: Efficient influence maximization in social networks. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 199\u2013208. Association for Computing Machinery, New York (2009)","DOI":"10.1145\/1557019.1557047"},{"key":"1406_CR14","doi-asserted-by":"crossref","unstructured":"Tang, Y., Xiao, X., Shi, Y.: Influence maximization: Near-optimal time complexity meets practical efficiency. In: Proc. ACM SIGMOD Int. Conf. Manage. Data, pp. 75\u201386. Association for Computing Machinery, New York (2014)","DOI":"10.1145\/2588555.2593670"},{"key":"1406_CR15","doi-asserted-by":"crossref","unstructured":"Tang, J., Tang, X., Yuan, J.: Influence maximization meets efficiency and effectiveness: a hop-based approach. In: Proc. IEEE\/ACM Int. Conf. Adv. Soc. Netw. Anal. Min., ASONAM, pp. 64\u201371. Association for Computing Machinery, New York (2017)","DOI":"10.1145\/3110025.3110041"},{"key":"1406_CR16","doi-asserted-by":"crossref","unstructured":"Chen, W., Lin, T., Tan, Z., Zhao, M., Zhou, X.: Robust influence maximization. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 795\u2013804. Association for Computing Machinery, New York (2016)","DOI":"10.1145\/2939672.2939745"},{"key":"1406_CR17","doi-asserted-by":"crossref","unstructured":"Zhang, H., Zhang, H., Kuhnle, A., Thai, M.T.: Profit maximization for multiple products in online social networks. In: Proc. IEEE INFOCOM, vol. 2016, pp. 1\u20139. Institute of Electrical and Electronics Engineers Inc., United States (2016)","DOI":"10.1109\/INFOCOM.2016.7524470"},{"issue":"6","key":"1406_CR18","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.: On budgeted influence maximization in social networks. IEEE J. Sel. Areas Commun. 31(6), 1084\u20131094 (2013)","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"1406_CR19","doi-asserted-by":"crossref","unstructured":"Lu, W., Lakshmanan, L.V.S.: Profit maximization over social networks. In: Proc. IEEE Int. Conf. Data Min. ICDM, pp. 479\u2013488. Institute of Electrical and Electronics Engineers Inc., United States (2012)","DOI":"10.1109\/ICDM.2012.145"},{"issue":"6","key":"1406_CR20","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1109\/TKDE.2017.2787757","volume":"30","author":"J Tang","year":"2018","unstructured":"Tang, J., Tang, X., Yuan, J.: Profit maximization for viral marketing in online social networks: algorithms and analysis. IEEE Trans. Knowl. Data Eng. 30(6), 1095\u20131108 (2018)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"1406_CR21","doi-asserted-by":"crossref","unstructured":"Bian, S., Guo, Q., Wang, S., Yu, J.X.: Efficient algorithms for budgeted influence maximization on massive social networks. In: Proc. VLDB Endow., Vol. 13, pp. 1498\u20131510. Springer, VLDB Endowment (2020)","DOI":"10.14778\/3397230.3397244"},{"key":"1406_CR22","doi-asserted-by":"publisher","first-page":"20040","DOI":"10.1109\/ACCESS.2019.2897608","volume":"7","author":"Y Zhang","year":"2019","unstructured":"Zhang, Y., Yang, X., Gao, S., Yang, W.: Budgeted profit maximization under the multiple products independent cascade model. IEEE Access 7, 20040\u201320049 (2019)","journal-title":"IEEE Access"},{"issue":"3","key":"1406_CR23","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1109\/TNSE.2020.2964882","volume":"7","author":"J Guo","year":"2020","unstructured":"Guo, J., Chen, T., Wu, W.: Budgeted coupon advertisement problem: algorithm and robust analysis. IEEE Trans. Netw. Sci. Eng. 7(3), 1966\u20131976 (2020)","journal-title":"IEEE Trans. Netw. Sci. Eng."},{"key":"1406_CR24","doi-asserted-by":"crossref","unstructured":"Tang, J., Tang, X., Yuan, J.: Profit maximization for viral marketing in online social networks. In: Proc. Int. Conf. Netw. Protoc. ICNP, vol. 2016, pp. 1\u201310. IEEE Computer Society, California (2016)","DOI":"10.1109\/ICNP.2016.7784445"},{"key":"1406_CR25","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1016\/j.tcs.2019.03.007","volume":"803","author":"B Liu","year":"2020","unstructured":"Liu, B., Li, X., Wang, H., Fang, Q., Dong, J., Wu, W.: Profit maximization problem with coupons in social networks. Theor. Comput. Sci. 803, 22\u201335 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1406_CR26","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1109\/TCSS.2021.3061452","volume":"8","author":"J Guo","year":"2021","unstructured":"Guo, J., Wu, W.: Continuous profit maximization: a study of unconstrained DR-submodular maximization. IEEE Trans. Comput. Soc. Syst. 8(3), 768\u2013779 (2021)","journal-title":"IEEE Trans. Comput. Soc. Syst."},{"issue":"4","key":"1406_CR27","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(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"key":"1406_CR28","doi-asserted-by":"crossref","unstructured":"Lu, C., Yang, W., Gao, S.: Regularized non-monotone submodular maximization. Optimization, 1\u201327 (2023)","DOI":"10.1007\/s10878-022-00965-9"},{"issue":"4","key":"1406_CR29","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1287\/moor.2016.0842","volume":"42","author":"M Sviridenko","year":"2017","unstructured":"Sviridenko, M., Vondrak, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4), 1197\u20131218 (2017)","journal-title":"Math. Oper. Res."},{"key":"1406_CR30","doi-asserted-by":"crossref","unstructured":"Nikolakaki, S.M., Ene, A., Terzi, E.: An efficient framework for balancing submodularity and cost. In: Proc. ACM SIGKDD Int. Conf. Knowl. Discov. Data Min., pp. 1256\u20131266. Association for Computing Machinery, New York (2021)","DOI":"10.1145\/3447548.3467367"},{"key":"1406_CR31","unstructured":"Harshaw, C., Feldman, M., Ward, J., Karbasi, A.: Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In: Int. Conf. Mach. Learn., ICML, vol. 2019, pp. 4684\u20134705. Association for Computing Machinery, New York (2019)"},{"issue":"3","key":"1406_CR32","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00453-020-00757-9","volume":"83","author":"M Feldman","year":"2021","unstructured":"Feldman, M.: Guess free maximization of submodular and linear sums. Algorithmica 83(3), 853\u2013878 (2021)","journal-title":"Algorithmica"},{"issue":"1","key":"1406_CR33","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"31","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 31(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"5","key":"1406_CR34","doi-asserted-by":"publisher","first-page":"1332","DOI":"10.1007\/s00453-022-01071-2","volume":"85","author":"M Feldman","year":"2023","unstructured":"Feldman, M., Nutov, Z., Shoham, E.: Practical budgeted submodular maximization. Algorithmica 85(5), 1332\u20131371 (2023)","journal-title":"Algorithmica"},{"key":"1406_CR35","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 2019), vol. 132, pp. 53\u201315312. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2019)"},{"key":"1406_CR36","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., Du, D.Z.: A fast and deterministic algorithm for knapsack-constrained monotone DR-submodular maximization over an integer lattice. J. Global Optim. 85, 15\u201338 (2023)","journal-title":"J. Global Optim."},{"issue":"3","key":"1406_CR37","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.: Constrained submodular maximization via a nonsymmetric technique. Math. Oper. Res. 44(3), 988\u20131005 (2019)","journal-title":"Math. Oper. Res."},{"key":"1406_CR38","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114293","volume":"984","author":"X Sun","year":"2024","unstructured":"Sun, X., Zhang, J., Zhang, S., Zhang, Z.: Improved deterministic algorithms for non-monotone submodular maximization. Theor. Comput. Sci. 984, 114293 (2024)","journal-title":"Theor. Comput. Sci."},{"issue":"10","key":"1406_CR39","first-page":"1756","volume":"14","author":"T Jin","year":"2021","unstructured":"Jin, T., Yang, Y., Yang, R., Shi, J., Huang, K., Xiao, X.: Unconstrained submodular maximization with modular costs: tight approximation and application to profit maximization. IEEE Trans. Computat. Soc. Syst. 14(10), 1756\u20131768 (2021)","journal-title":"IEEE Trans. Computat. Soc. Syst."},{"key":"1406_CR40","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s10898-004-5909-z","volume":"32","author":"B Goldengorin","year":"2005","unstructured":"Goldengorin, B., Ghosh, D.: A multilevel search algorithm for the maximization of submodular functions applied to the quadratic cost partition problem. J. Global Optim. 32, 65\u201382 (2005)","journal-title":"J. Global Optim."},{"key":"1406_CR41","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113847","volume":"957","author":"S Gu","year":"2023","unstructured":"Gu, S., Gao, C., Huang, J., Wu, W.: Profit maximization in social networks and non-monotone DR-submodular maximization. Theor. Comput. Sci. 957, 113847 (2023)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1406_CR42","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1007\/s10618-022-00833-4","volume":"36","author":"G Zhang","year":"2022","unstructured":"Zhang, G., Tatti, N., Gionis, A.: Ranking with submodular functions on a budget. Data Min. Knowl. Disc. 36(3), 1197\u20131218 (2022)","journal-title":"Data Min. Knowl. Disc."}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01406-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-024-01406-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01406-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T14:03:02Z","timestamp":1730296982000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-024-01406-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,14]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["1406"],"URL":"https:\/\/doi.org\/10.1007\/s10898-024-01406-z","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"value":"0925-5001","type":"print"},{"value":"1573-2916","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,14]]},"assertion":[{"value":"8 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2024","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 declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}