{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:36:15Z","timestamp":1767339375085,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,4,25]],"date-time":"2016-04-25T00:00:00Z","timestamp":1461542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,6,15]]},"abstract":"<jats:p>\n            We study a variant of the\n            <jats:italic>generalized assignment problem<\/jats:italic>\n            (\n            <jats:sc>gap<\/jats:sc>\n            ), which we label\n            <jats:italic>all-or-nothing<\/jats:italic>\n            <jats:sc>gap<\/jats:sc>\n            (\n            <jats:sc>agap<\/jats:sc>\n            ). We are given a set of items, partitioned into\n            <jats:italic>n<\/jats:italic>\n            groups, and a set of\n            <jats:italic>m<\/jats:italic>\n            bins. Each item \u2113 has size\n            <jats:italic>s<\/jats:italic>\n            <jats:sub>\u2113<\/jats:sub>\n            &gt; 0, and utility\n            <jats:italic>a<\/jats:italic>\n            <jats:sub>\n              \u2113\n              <jats:italic>j<\/jats:italic>\n            <\/jats:sub>\n            \u2a7e 0 if packed in bin\n            <jats:italic>j<\/jats:italic>\n            . Each bin can accommodate at most one item from each group; the total size of the items in a bin cannot exceed its capacity. A group of items is\n            <jats:italic>satisfied<\/jats:italic>\n            if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total utility from satisfied groups is maximized. We motivate the study of\n            <jats:sc>agap<\/jats:sc>\n            by pointing out a central application in scheduling advertising campaigns.\n          <\/jats:p>\n          <jats:p>\n            Our main result is an\n            <jats:italic>O<\/jats:italic>\n            (1)-approximation algorithm for\n            <jats:sc>agap<\/jats:sc>\n            instances arising in practice, in which each group consists of at most\n            <jats:italic>m<\/jats:italic>\n            \/2 items. Our algorithm uses a novel reduction of\n            <jats:sc>agap<\/jats:sc>\n            to maximizing submodular function subject to a matroid constraint. For\n            <jats:sc>agap<\/jats:sc>\n            instances with a fixed number of bins, we develop a randomized\n            <jats:italic>polynomial time approximation scheme (PTAS)<\/jats:italic>\n            , relying on a nontrivial LP relaxation of the problem.\n          <\/jats:p>\n          <jats:p>\n            We present a (3 + \u03b5)-approximation as well as PTASs for other special cases of\n            <jats:sc>agap<\/jats:sc>\n            , where the utility of any item does not depend on the bin in which it is packed. Finally, we derive hardness results for the different variants of\n            <jats:sc>agap<\/jats:sc>\n            studied in this paper.\n          <\/jats:p>","DOI":"10.1145\/2843944","type":"journal-article","created":{"date-parts":[[2016,4,25]],"date-time":"2016-04-25T19:51:13Z","timestamp":1461613873000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["All-Or-Nothing Generalized Assignment with Application to Scheduling Advertising Campaigns"],"prefix":"10.1145","volume":"12","author":[{"given":"Ron","family":"Adany","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1535-2979","authenticated-orcid":false,"given":"Moran","family":"Feldman","sequence":"additional","affiliation":[{"name":"Technion"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elad","family":"Haramaty","sequence":"additional","affiliation":[{"name":"Technion"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rohit","family":"Khandekar","sequence":"additional","affiliation":[{"name":"Knight Capital Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[{"name":"IBM Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roy","family":"Schwartz","sequence":"additional","affiliation":[{"name":"Microsoft Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hadas","family":"Shachnai","sequence":"additional","affiliation":[{"name":"Technion"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tami","family":"Tamir","sequence":"additional","affiliation":[{"name":"The Interdisciplinary Center, Herzliya, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,4,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00530-012-0284-y"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000038913.96607.c2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799356265"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 2nd European Conference on Interactive Television: Enhancing the Experience","author":"Dureau V.","year":"2004","unstructured":"V. Dureau . 2004 . Addressable advertising on digital television . In Proceedings of the 2nd European Conference on Interactive Television: Enhancing the Experience . Brighton, UK. V. Dureau. 2004. Addressable advertising on digital television. In Proceedings of the 2nd European Conference on Interactive Television: Enhancing the Experience. Brighton, UK."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.14"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0499"},{"key":"e_1_2_1_10_1","unstructured":"M. R. Garey and D. S. Johnson. 1979. Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman New York NY.   M. R. Garey and D. S. Johnson. 1979. Computers and Intractability. A Guide to the Theory of NP-Completeness. W. H. Freeman New York NY."},{"key":"e_1_2_1_11_1","unstructured":"Google AdWords. 2013. Retrieved March 20 2016 from http:\/\/adwords.google.com.  Google AdWords. 2013. Retrieved March 20 2016 from http:\/\/adwords.google.com."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1207\/s15327736me1901_4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"A. Kulik H. Shachnai and T. Tamir. 2009. Maximizing submodular set functions subject to multiple linear constraints. In SODA. 545--554.   A. Kulik H. Shachnai and T. Tamir. 2009. Maximizing submodular set functions subject to multiple linear constraints. In SODA. 545--554.","DOI":"10.1137\/1.9781611973068.60"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0592"},{"volume-title":"Encyclopedia of Optimization, Christodoulos A","author":"Erhun Kundakcioglu O.","key":"e_1_2_1_15_1","unstructured":"O. Erhun Kundakcioglu and Saed Alizamir . 2009. Generalized assignment problem . In Encyclopedia of Optimization, Christodoulos A . Floudas and Panos M. Pardalos (Eds.). Springer , 1153--1162. O. Erhun Kundakcioglu and Saed Alizamir. 2009. Generalized assignment problem. In Encyclopedia of Optimization, Christodoulos A. Floudas and Panos M. Pardalos (Eds.). Springer, 1153--1162."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/98124"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_18_1","volume-title":"Advertising Fact Sheet. blog.nielsen.com. (September","author":"Research Nielsen Media","year":"2010","unstructured":"Nielsen Media Research . 2010. Advertising Fact Sheet. blog.nielsen.com. (September 2010 ). Nielsen Media Research. 2010. Advertising Fact Sheet. blog.nielsen.com. (September 2010)."},{"key":"e_1_2_1_19_1","volume-title":"Retrieved","author":"Research Nielsen Media","year":"2012","unstructured":"Nielsen Media Research . 2012 a. The cross-platform report, quarter 1, 2012 -- US . Retrieved March 20, 2016 from blog.nielsen.com. Nielsen Media Research. 2012a. The cross-platform report, quarter 1, 2012 -- US. Retrieved March 20, 2016 from blog.nielsen.com."},{"key":"e_1_2_1_20_1","volume-title":"Retrieved","author":"Research Nielsen Media","year":"2012","unstructured":"Nielsen Media Research . 2012 b. Nielsen\u2019s quarterly Global AdView Pulse Report . Retrieved March 20, 2016 from blog.nielsen.com. Nielsen Media Research. 2012b. Nielsen\u2019s quarterly Global AdView Pulse Report. Retrieved March 20, 2016 from blog.nielsen.com."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2005.05.006"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/767674.768092"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/10196780151105348"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/3113606.3113856"},{"key":"e_1_2_1_25_1","unstructured":"SintecMedia - On Air. 2013. Retrieved March 20 2016 from http:\/\/www.sintecmedia.com\/OnAir.html.  SintecMedia - On Air. 2013. Retrieved March 20 2016 from http:\/\/www.sintecmedia.com\/OnAir.html."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"e_1_2_1_27_1","unstructured":"The Interactive Advertising Bureau (IAB). 2013. Retrieved March 20 2016 from http:\/\/iab.net. (2013).  The Interactive Advertising Bureau (IAB). 2013. Retrieved March 20 2016 from http:\/\/iab.net. (2013)."},{"key":"e_1_2_1_28_1","first-page":"45","article-title":"Why TV spot length matters","volume":"497","author":"Young C.","year":"2008","unstructured":"C. Young . 2008 . Why TV spot length matters . Admap 497 , 45 -- 48 . C. Young. 2008. Why TV spot length matters. Admap 497, 45--48.","journal-title":"Admap"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2843944","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2843944","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:48:51Z","timestamp":1750225731000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2843944"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,25]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6,15]]}},"alternative-id":["10.1145\/2843944"],"URL":"https:\/\/doi.org\/10.1145\/2843944","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2016,4,25]]},"assertion":[{"value":"2014-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-04-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}