{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T06:05:45Z","timestamp":1648620345185},"reference-count":37,"publisher":"VLDB Endowment","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,6]]},"abstract":"\n Given a set\n V<\/jats:italic>\n , the problem of\n unconstrained submodular maximization with modular costs (USM-MC)<\/jats:italic>\n asks for a subset\n S<\/jats:italic>\n \u2286\n V<\/jats:italic>\n that maximizes\n f<\/jats:italic>\n (\n S<\/jats:italic>\n ) -\n c<\/jats:italic>\n (\n S<\/jats:italic>\n ), where\n f<\/jats:italic>\n is a non-negative, monotone, and submodular function that gauges the utility of\n S<\/jats:italic>\n , and\n c<\/jats:italic>\n is a non-negative and modular function that measures the cost of\n 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 \n This paper presents ROI-Greedy, a polynomial time algorithm for USM-MC that returns a solution\n S<\/jats:italic>\n satisfying [EQUATION], where\n S<\/jats:italic>\n *<\/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 tight<\/jats:italic>\n , in the sense that no polynomial time algorithm can ensure [EQUATION], for any \u03f5 > 0. Further, we devise a non-trivial extension of ROI-Greedy to solve the profit maximization problem, where the precise value of\n f<\/jats:italic>\n (\n S<\/jats:italic>\n ) for any set\n 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":0,"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"}]},{"given":"Yu","family":"Yang","sequence":"additional","affiliation":[{"name":"City University of Hong Kong"}]},{"given":"Renchi","family":"Yang","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Jieming","family":"Shi","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University"}]},{"given":"Keke","family":"Huang","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"National University of Singapore"}]}],"member":"5777","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":[[2021,10,26]],"date-time":"2021-10-26T16:22:40Z","timestamp":1635265360000},"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":"http:\/\/dx.doi.org\/10.14778\/3467861.3467866","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":["General Earth and Planetary Sciences","Water Science and Technology","Geography, Planning and Development"],"published":{"date-parts":[[2021,6]]}}}