{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:17:03Z","timestamp":1785543423211,"version":"3.56.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:p>\n            Given a set\n            <jats:italic>V<\/jats:italic>\n            , the problem of\n            <jats:italic>unconstrained submodular maximization with modular costs (USM-MC)<\/jats:italic>\n            asks for a subset\n            <jats:italic>S<\/jats:italic>\n            \u2286\n            <jats:italic>V<\/jats:italic>\n            that maximizes\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>S<\/jats:italic>\n            ) -\n            <jats:italic>c<\/jats:italic>\n            (\n            <jats:italic>S<\/jats:italic>\n            ), where\n            <jats:italic>f<\/jats:italic>\n            is a non-negative, monotone, and submodular function that gauges the utility of\n            <jats:italic>S<\/jats:italic>\n            , and\n            <jats:italic>c<\/jats:italic>\n            is a non-negative and modular function that measures the cost of\n            <jats:italic>S.<\/jats:italic>\n            This problem finds applications in numerous practical scenarios, such as profit maximization in viral marketing on social media.\n          <\/jats:p>\n          <jats:p>\n            This paper presents ROI-Greedy, a polynomial time algorithm for USM-MC that returns a solution\n            <jats:italic>S<\/jats:italic>\n            satisfying [EQUATION], where\n            <jats:italic>S<\/jats:italic>\n            <jats:sup>*<\/jats:sup>\n            is the optimal solution to USM-MC. To our knowledge, ROI-Greedy is the first algorithm that provides such a strong approximation guarantee. In addition, we show that this worst-case guarantee is\n            <jats:italic>tight<\/jats:italic>\n            , in the sense that no polynomial time algorithm can ensure [EQUATION], for any \u03f5 &gt; 0. Further, we devise a non-trivial extension of ROI-Greedy to solve the profit maximization problem, where the precise value of\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>S<\/jats:italic>\n            ) for any set\n            <jats:italic>S<\/jats:italic>\n            is unknown and can only be approximated via sampling. Extensive experiments on benchmark datasets demonstrate that ROI-Greedy significantly outperforms competing methods in terms of the tradeoff between efficiency and solution quality.\n          <\/jats:p>","DOI":"10.14778\/3467861.3467866","type":"journal-article","created":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T16:17:12Z","timestamp":1635265032000},"page":"1756-1768","source":"Crossref","is-referenced-by-count":25,"title":["Unconstrained submodular maximization with modular costs"],"prefix":"10.14778","volume":"14","author":[{"given":"Tianyuan","family":"Jin","sequence":"first","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yu","family":"Yang","sequence":"additional","affiliation":[{"name":"City University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Renchi","family":"Yang","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jieming","family":"Shi","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Keke","family":"Huang","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_11"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397244"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634144"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.73"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839655"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591884"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Alina Ene and Huy L Nguyen. 2016. Constrained submodular maximization: Beyond 1\/e. In FOCS. 248--257.  Alina Ene and Huy L Nguyen. 2016. Constrained submodular maximization: Beyond 1\/e. In FOCS. 248--257.","DOI":"10.1109\/FOCS.2016.34"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_11_1","volume-title":"Guess free maximization of submodular and linear sums. Algorithmica","author":"Feldman Moran","year":"2020","unstructured":"Moran Feldman . 2020. Guess free maximization of submodular and linear sums. Algorithmica ( 2020 ), 1--26. Moran Feldman. 2020. Guess free maximization of submodular and linear sums. Algorithmica (2020), 1--26."},{"key":"e_1_2_1_12_1","unstructured":"Chris Harshaw Moran Feldman Justin Ward and Amin Karbasi. 2019. Submodular Maximization beyond Non-negativity: Guarantees Fast Algorithms and Applications. In ICML. 2634--2643.  Chris Harshaw Moran Feldman Justin Ward and Amin Karbasi. 2019. Submodular Maximization beyond Non-negativity: Guarantees Fast Algorithms and Applications. In ICML. 2634--2643."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Keke Huang Jing Tang Xiaokui Xiao Aixin Sun and Andrew Lim. 2020. Efficient approximation algorithms for adaptive target profit maximization. In ICDE. 649--660.  Keke Huang Jing Tang Xiaokui Xiao Aixin Sun and Andrew Lim. 2020. Efficient approximation algorithms for adaptive target profit maximization. In ICDE. 649--660.","DOI":"10.1109\/ICDE48307.2020.00062"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099623"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999792.2999884"},{"key":"e_1_2_1_16_1","volume-title":"Regularized Submodular Maximization at Scale. arXiv preprint arXiv:2002.03503","author":"Kazemi Ehsan","year":"2020","unstructured":"Ehsan Kazemi , Shervin Minaee , Moran Feldman , and Amin Karbasi . 2020. Regularized Submodular Maximization at Scale. arXiv preprint arXiv:2002.03503 ( 2020 ). Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi. 2020. Regularized Submodular Maximization at Scale. arXiv preprint arXiv:2002.03503 (2020)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1619797.1619913"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_19"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_22_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1857999.1858133"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2002472.2002537"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.145"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2886521.2886572"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/3134214"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0842"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319881"},{"key":"e_1_2_1_32_1","volume-title":"Profit maximization for viral marketing in online social networks","author":"Tang Jing","unstructured":"Jing Tang , Xueyan Tang , and Junsong Yuan . 2016. Profit maximization for viral marketing in online social networks . In ICNP. IEEE , 1--10. Jing Tang, Xueyan Tang, and Junsong Yuan. 2016. Profit maximization for viral marketing in online social networks. In ICNP. IEEE, 1--10."},{"key":"e_1_2_1_33_1","first-page":"1095","article-title":"Profit maximization for viral marketing in online social networks: Algorithms and analysis","volume":"30","author":"Tang Jing","year":"2017","unstructured":"Jing Tang , Xueyan Tang , and Junsong Yuan . 2017 . Profit maximization for viral marketing in online social networks: Algorithms and analysis . TKDE 30 , 6 (2017), 1095 -- 1108 . Jing Tang, Xueyan Tang, and Junsong Yuan. 2017. Profit maximization for viral marketing in online social networks: Algorithms and analysis. TKDE 30, 6 (2017), 1095--1108.","journal-title":"TKDE"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Jing Tang Xueyan Tang and Junsong Yuan. 2018. Towards profit maximization for online social network providers. In INFOCOM. 1178--1186.  Jing Tang Xueyan Tang and Junsong Yuan. 2018. Towards profit maximization for online social network providers. In INFOCOM. 1178--1186.","DOI":"10.1109\/INFOCOM.2018.8485975"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2017.2715183"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Yuqing Zhu Zaixin Lu Yuanjun Bi Weili Wu Yiwei Jiang and Deying Li. 2013. Influence and profit: Two sides of the coin. In ICDM. 1301--1306.  Yuqing Zhu Zaixin Lu Yuanjun Bi Weili Wu Yiwei Jiang and Deying Li. 2013. Influence and profit: Two sides of the coin. In ICDM. 1301--1306.","DOI":"10.1109\/ICDM.2013.40"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3467861.3467866","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:34:03Z","timestamp":1672223643000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3467861.3467866"}},"subtitle":["tight approximation and application to profit maximization"],"short-title":[],"issued":{"date-parts":[[2021,6]]},"references-count":37,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["10.14778\/3467861.3467866"],"URL":"https:\/\/doi.org\/10.14778\/3467861.3467866","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,6]]}}}