{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,25]],"date-time":"2026-06-25T05:02:59Z","timestamp":1782363779671,"version":"3.54.5"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,2]]},"abstract":"<jats:p>Social advertisement is one of the fastest growing sectors in the digital advertisement landscape: ads in the form of promoted posts are shown in the feed of users of a social networking platform, along with normal social posts; if a user clicks on a promoted post, the host (social network owner) is paid a fixed amount from the advertiser. In this context, allocating ads to users is typically performed by maximizing click-through-rate, i.e., the likelihood that the user will click on the ad. However, this simple strategy fails to leverage the fact the ads can propagate virally through the network, from endorsing users to their followers.<\/jats:p>\n          <jats:p>In this paper, we study the problem of allocating ads to users through the viral-marketing lenses. We show that allocation that takes into account the propensity of ads for viral propagation can achieve significantly better performance. However, uncontrolled virality could be undesirable for the host as it creates room for exploitation by the advertisers: hoping to tap uncontrolled virality, an advertiser might declare a lower budget for its marketing campaign, aiming at the same large outcome with a smaller cost.<\/jats:p>\n          <jats:p>This creates a challenging trade-off: on the one hand, the host aims at leveraging virality and the network effect to improve advertising efficacy, while on the other hand the host wants to avoid giving away free service due to uncontrolled virality. We formalize this as the problem of ad allocation with minimum regret, which we show is NP-hard and inapproximable w.r.t. any factor. However, we devise an algorithm that provides approximation guarantees w.r.t. the total budget of all advertisers. We develop a scalable version of our approximation algorithm, which we extensively test on four real-world data sets, confirming that our algorithm delivers high quality solutions, is scalable, and significantly outperforms several natural baselines.<\/jats:p>","DOI":"10.14778\/2752939.2752950","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"814-825","source":"Crossref","is-referenced-by-count":52,"title":["Viral marketing meets social advertising"],"prefix":"10.14778","volume":"8","author":[{"given":"Cigdem","family":"Aslay","sequence":"first","affiliation":[{"name":"Univ. Pompeu Fabra, Barcelona, Spain and Yahoo Labs, Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei","family":"Lu","sequence":"additional","affiliation":[{"name":"Univ. of British Columbia, Vancouver, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francesco","family":"Bonchi","sequence":"additional","affiliation":[{"name":"Yahoo Labs, Barcelona, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amit","family":"Goyal","sequence":"additional","affiliation":[{"name":"Twitter, San Francisco, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laks V. S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"Univ. of British Columbia, Vancouver, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret. arXiv:1412.1462","author":"Aslay C.","year":"2014","unstructured":"C. Aslay Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret. arXiv:1412.1462 , 2014 . C. Aslay et al. Viral Marketing Meets Social Advertising: Ad Allocation with Minimum Regret. arXiv:1412.1462, 2014."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229027"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.122"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/944919.944937"},{"key":"e_1_2_1_5_1","first-page":"946","volume-title":"SODA","author":"Borgs C.","year":"2014","unstructured":"C. Borgs Maximizing social influence in nearly optimal time . In SODA , pp. 946 -- 957 . SIAM , 2014 . C. Borgs et al. Maximizing social influence in nearly optimal time. In SODA, pp. 946--957. SIAM, 2014."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/993483"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2662077"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.52"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229043"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/318242.318443"},{"key":"e_1_2_1_12_1","volume-title":"Budgeted influence maximization for multiple products. arXiv:1312.2164","author":"Du N.","year":"2014","unstructured":"N. Du Budgeted influence maximization for multiple products. arXiv:1312.2164 , 2014 . N. Du et al. Budgeted influence maximization for multiple products. arXiv:1312.2164, 2014."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888935.1888957"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_34"},{"key":"e_1_2_1_15_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . New York, NY , 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY, 1979."},{"key":"e_1_2_1_16_1","first-page":"982","volume-title":"SODA","author":"Goel G.","year":"2008","unstructured":"G. Goel Online budgeted matching in random input models with applications to adwords . In SODA , pp. 982 -- 991 , 2008 . G. Goel et al. Online budgeted matching in random input models with applications to adwords. In SODA, pp. 982--991, 2008."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2047485.2047492"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.79"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2014.131"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095250"},{"key":"e_1_2_1_23_1","volume-title":"Mathematical Programming","author":"Nemhauser G. L.","year":"1978","unstructured":"G. L. Nemhauser , L. A. Wolsey , and M. L. Fisher . An analysis of approximations for maximizing submodular set functions - i . Mathematical Programming , 1978 . G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions - i. Mathematical Programming, 1978."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593670"},{"key":"e_1_2_1_25_1","volume-title":"Social advertising. Working paper available at SSRN: http:\/\/ssrn.com\/abstract=1975897","author":"Tucker C.","year":"2012","unstructured":"C. Tucker . Social advertising. Working paper available at SSRN: http:\/\/ssrn.com\/abstract=1975897 , 2012 . C. Tucker. Social advertising. Working paper available at SSRN: http:\/\/ssrn.com\/abstract=1975897, 2012."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2752939.2752950","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:14:45Z","timestamp":1672222485000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2752939.2752950"}},"subtitle":["ad allocation with minimum regret"],"short-title":[],"issued":{"date-parts":[[2015,2]]},"references-count":25,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2015,2]]}},"alternative-id":["10.14778\/2752939.2752950"],"URL":"https:\/\/doi.org\/10.14778\/2752939.2752950","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,2]]}}}