{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:25:49Z","timestamp":1778495149193,"version":"3.51.4"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","license":[{"start":{"date-parts":[[2018,10,10]],"date-time":"2018-10-10T00:00:00Z","timestamp":1539129600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ISF","award":["1585\/15"],"award-info":[{"award-number":["1585\/15"]}]},{"name":"United States-Israel BSF","award":["2014414"],"award-info":[{"award-number":["2014414"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2018,11,30]]},"abstract":"<jats:p>\n            Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established that these problems admit no randomized online algorithm better than (1 - 1\/\n            <jats:italic>e<\/jats:italic>\n            )-competitive (see Karp et al. (1990) and Mehta et al. (2007)), yet simple heuristics have been observed to perform much better in practice. We explain this phenomenon by studying a generalization of the bounded-degree inputs considered by Buchbinder et al. (2007), graphs which we call (\n            <jats:italic>k<\/jats:italic>\n            ,\n            <jats:italic>d<\/jats:italic>\n            )-\n            <jats:italic>bounded<\/jats:italic>\n            . In such graphs the maximal degree on the online side is at most\n            <jats:italic>d<\/jats:italic>\n            and the minimal degree on the offline side is at least\n            <jats:italic>k<\/jats:italic>\n            . We prove that, for such graphs, these problems\u2019 natural greedy algorithms attain a competitive ratio of 1 -\n            <jats:italic>d<\/jats:italic>\n            -1\/\n            <jats:italic>k<\/jats:italic>\n            +\n            <jats:italic>d<\/jats:italic>\n            -1, tending to\n            <jats:italic>1<\/jats:italic>\n            as\n            <jats:italic>d<\/jats:italic>\n            \/\n            <jats:italic>k<\/jats:italic>\n            tends to zero. We prove this bound is tight for these algorithms.\n          <\/jats:p>\n          <jats:p>\n            Next, we develop deterministic primal-dual algorithms for the above problems, achieving a competitive ratio of 1\u2212(1 - 1\/\n            <jats:italic>d<\/jats:italic>\n            )\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            &gt; 1 - &amp;1\/\n            <jats:italic>e<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n              \/\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            , or\n            <jats:italic>exponentially<\/jats:italic>\n            better loss as a function of\n            <jats:italic>k<\/jats:italic>\n            \/\n            <jats:italic>\/d<\/jats:italic>\n            , and strictly better than 1 - 1\/e whenever\n            <jats:italic>k<\/jats:italic>\n            \u2265\n            <jats:italic>d<\/jats:italic>\n            . We complement our lower bounds with matching upper bounds for the vertex-weighted problem. Finally, we use our deterministic algorithms to prove by dual-fitting that simple randomized algorithms achieve the same bounds in expectation. Our algorithms and analysis differ from previous ad allocation algorithms, which largely scale bids based on the spent fraction of their bidder\u2019s budget, whereas we scale bids according to the number of times the bidder could have spent as much as her current bid. Our algorithms differ from previous online primal-dual algorithms in that they do not maintain dual feasibility but only a primal-to-dual ratio and only attain dual feasibility upon termination. We believe our techniques could find applications to other well-behaved online packing problems.\n          <\/jats:p>","DOI":"10.1145\/3105447","type":"journal-article","created":{"date-parts":[[2018,10,10]],"date-time":"2018-10-10T13:30:46Z","timestamp":1539178246000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Near-Optimum Online Ad Allocation for Targeted Advertising"],"prefix":"10.1145","volume":"6","author":[{"given":"Joseph (Seffi)","family":"Naor","sequence":"first","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Wajc","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,10,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_68"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133131"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888935.1888956"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360443.1360462"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778606"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000024"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Cohen Ilan R."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1998549.1998558"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566384"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 101--107","author":"Devanur Nikhil R."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229043"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888935.1888957"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.72"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 982--991","author":"Goel Gagan","year":"2008"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25510-6_15"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00140-1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993715"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250910.1250952"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993716"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0551"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095250"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764482"},{"key":"e_1_2_1_27_1","unstructured":"PriceWaterHouseCoopers. 2018. IAB Internet advertising revenue report - 2017 full year results. (2018). https:\/\/www.iab.com\/wp-content\/uploads\/2018\/05\/IAB-2017-Full-Year-Internet-Advertising-Revenue-Report.REV2_.pdf {Online; accessed 27 September 2018}.  PriceWaterHouseCoopers. 2018. IAB Internet advertising revenue report - 2017 full year results. (2018). https:\/\/www.iab.com\/wp-content\/uploads\/2018\/05\/IAB-2017-Full-Year-Internet-Advertising-Revenue-Report.REV2_.pdf {Online; accessed 27 September 2018}."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105447","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3105447","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:38Z","timestamp":1750217438000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105447"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,10]]},"references-count":28,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2018,11,30]]}},"alternative-id":["10.1145\/3105447"],"URL":"https:\/\/doi.org\/10.1145\/3105447","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,10,10]]},"assertion":[{"value":"2016-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}