TY - GEN
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
PY - 2013
Y1 - 2013
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 m bins. Each item ℓ has size sℓ > 0, and utility aℓj ≥ 0 if packed in bin j. Each bin can accommodate at most one item from each group, and 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, where 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 fixed number of bins, we develop a randomized polynomial time approximation scheme (PTAS), relying on a non-trivial 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 the 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 m bins. Each item ℓ has size sℓ > 0, and utility aℓj ≥ 0 if packed in bin j. Each bin can accommodate at most one item from each group, and 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, where 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 fixed number of bins, we develop a randomized polynomial time approximation scheme (PTAS), relying on a non-trivial 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 the paper.
UR - http://www.scopus.com/inward/record.url?scp=84875499475&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84875499475&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-36694-9_2
DO - 10.1007/978-3-642-36694-9_2
M3 - Conference contribution
AN - SCOPUS:84875499475
SN - 9783642366932
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 13
EP - 24
BT - Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Proceedings
T2 - 16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013
Y2 - 18 March 2013 through 20 March 2013
ER -