{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:59Z","timestamp":1740122459627,"version":"3.37.3"},"reference-count":9,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T00:00:00Z","timestamp":1728777600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T00:00:00Z","timestamp":1728777600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["1948550"],"award-info":[{"award-number":["1948550"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100009482","name":"Santa Clara University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009482","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Given a monotone submodular set function with a knapsack constraint, its maximization problem has two types of approximation algorithms with running time <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^5)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>5<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, respectively. With running time <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^5)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>5<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the best performance ratio is <jats:inline-formula><jats:alternatives><jats:tex-math>$$1-1\/e$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mi>e<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. With running time <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, the well-known performance ratio is <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1-1\/e)\/2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mi>e<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and an improved one is claimed to be <jats:inline-formula><jats:alternatives><jats:tex-math>$$(1-1\/e^2)\/2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>e<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> recently. In this paper, we design an algorithm with running <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^2)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>2<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and performance ratio <jats:inline-formula><jats:alternatives><jats:tex-math>$$1-1\/e^{2\/3}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>e<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>3<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and an algorithm with running time <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^3)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mn>3<\/mml:mn>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and performance ratio 1\/2.\n<\/jats:p>","DOI":"10.1007\/s10878-024-01214-x","type":"journal-article","created":{"date-parts":[[2024,10,13]],"date-time":"2024-10-13T21:01:43Z","timestamp":1728853303000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["New approximations for monotone submodular maximization with knapsack constraint"],"prefix":"10.1007","volume":"48","author":[{"given":"Hongmin W.","family":"Du","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7761-6212","authenticated-orcid":false,"given":"Xiang","family":"Li","sequence":"additional","affiliation":[]},{"given":"Guanghua","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,10,13]]},"reference":[{"issue":"2","key":"1214_CR1","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1109\/TCSS.2018.2813262","volume":"5","author":"K Alan","year":"2018","unstructured":"Alan K, Abdul AM, Xiang L, Huiling Z, Thai My T (2018) Multiplex influence maximization in online social networks with heterogeneous diffusion models. IEEE Trans Comput Social Syst 5(2):418\u2013429","journal-title":"IEEE Trans Comput Social Syst"},{"key":"1214_CR2","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2019.03.028","volume":"803","author":"T Chen","year":"2020","unstructured":"Chen T, Liu B, Liu W, Fang Q, Yuan J, Weili W (2020) A random algorithm for profit maximization in online social networks. Theor Comput Sci 803:36\u201347","journal-title":"Theor Comput Sci"},{"key":"1214_CR3","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.tcs.2019.03.028","volume":"803","author":"T Chen","year":"2020","unstructured":"Chen T, Liu B, Liu W, Fang Q, Yuan J, Weili W (2020) A random algorithm for profit maximization in online social networks. Theor Comput Sci 803:36\u201347","journal-title":"Theor Comput Sci"},{"key":"1214_CR4","doi-asserted-by":"crossref","unstructured":"Zhang Huiyuan, Zhang Huiling, Kuhnle Alan, Thai My\u00a0T (2016) Profit maximization for multiple products in online social networks. In IEEE INFOCOM 2016-The 35th Annual IEEE International Conference on Computer Communications, pages 1\u20139. IEEE","DOI":"10.1109\/INFOCOM.2016.7524470"},{"key":"1214_CR5","doi-asserted-by":"crossref","unstructured":"Guo Jianxiong, Wu Weili (2019) Viral marketing for complementary products. Nonlinear Combinatorial Optimization, pages 309\u2013315","DOI":"10.1007\/978-3-030-16194-1_16"},{"issue":"4","key":"1214_CR6","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 (JACM) 45(4):634\u2013652","journal-title":"J ACM (JACM)"},{"issue":"1","key":"1214_CR7","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"},{"key":"1214_CR8","doi-asserted-by":"crossref","unstructured":"Leskovec Jure, Krause Andreas, Guestrin Carlos, Faloutsos Christos, VanBriesen Jeanne, Glance Natalie (2007) Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 420\u2013429","DOI":"10.1145\/1281192.1281239"},{"key":"1214_CR9","doi-asserted-by":"crossref","unstructured":"Du Dingzhu, Pardalos Panos\u00a0M, Hu Xiaodong, Wu Weili, et\u00a0al (2022) Introduction to combinatorial optimization. Springer","DOI":"10.1007\/978-3-031-10596-8"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01214-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01214-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01214-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,7]],"date-time":"2024-11-07T11:04:42Z","timestamp":1730977482000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01214-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,13]]},"references-count":9,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["1214"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01214-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,10,13]]},"assertion":[{"value":"22 September 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 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 interest"}}],"article-number":"28"}}