TY - JOUR

T1 - All-or-nothing generalized assignment with application to scheduling advertising campaigns

AU - Adany, Ron

AU - Feldman, Moran

AU - Haramaty, Elad

AU - Khandekar, Rohit

AU - Schieber, Baruch

AU - Schwartz, Roy

AU - Shachnai, Hadas

AU - Tamir, Tami

N1 - Publisher Copyright:
© 2016 ACM.

PY - 2016/4

Y1 - 2016/4

N2 - We study a variant of the generalized assignment problem (GAP), which we label all-or-nothing GAP (AGAP). We are given a set of items, partitioned into n groups, and a set of mbins. Each item ℓ has size sℓ > 0, and utility α ℓj ≥ 0 if packed in bin j. 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 satisfied 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 AGAP by pointing out a central application in scheduling advertising campaigns. Our main result is an O(1)-approximation algorithm for AGAP instances arising in practice, in which each group consists of at most m/2 items. Our algorithm uses a novel reduction of AGAP to maximizing submodular function subject to a matroid constraint. For AGAP instances with a fixed number of bins, we develop a randomized polynomial time approximation scheme (PTAS), relying on a nontrivial LP relaxation of the problem. We present a (3+ϵ)-approximation as well as PTASs for other special cases of AGAP, 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 AGAP studied in this paper.

AB - We study a variant of the generalized assignment problem (GAP), which we label all-or-nothing GAP (AGAP). We are given a set of items, partitioned into n groups, and a set of mbins. Each item ℓ has size sℓ > 0, and utility α ℓj ≥ 0 if packed in bin j. 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 satisfied 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 AGAP by pointing out a central application in scheduling advertising campaigns. Our main result is an O(1)-approximation algorithm for AGAP instances arising in practice, in which each group consists of at most m/2 items. Our algorithm uses a novel reduction of AGAP to maximizing submodular function subject to a matroid constraint. For AGAP instances with a fixed number of bins, we develop a randomized polynomial time approximation scheme (PTAS), relying on a nontrivial LP relaxation of the problem. We present a (3+ϵ)-approximation as well as PTASs for other special cases of AGAP, 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 AGAP studied in this paper.

KW - Ad placement

KW - Approximation algorithms

KW - Generalized assignment problem

KW - Group packing

UR - http://www.scopus.com/inward/record.url?scp=84968873950&partnerID=8YFLogxK

U2 - 10.1145/2843944

DO - 10.1145/2843944

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:84968873950

SN - 1549-6325

VL - 12

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 3

M1 - 38

ER -