TY - GEN
T1 - Generalized assignment via submodular optimization with reserved capacity
AU - Kulik, Ariel
AU - Sarpatwar, Kanthi
AU - Schieber, Baruch
AU - Shachnai, Hadas
N1 - Publisher Copyright:
© Ariel Kulik, Kanthi Sarpatwar, Baruch Schieber, and Hadas Shachnai.
PY - 2019/9
Y1 - 2019/9
N2 - We study a variant of the generalized assignment problem (GAP) with group constraints. An instance of Group GAP is a set I of items, partitioned into L groups, and a set of m uniform (unit-sized) bins. Each item i ϵ I has a size si > 0, and a profit pi,j ≥ 0 if packed in bin j. 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 profit from satisfied groups is maximized. We point to central applications of Group GAP in Video-on-Demand services, mobile Device-to-Device network caching and base station cooperation in 5G networks. Our main result is a 1/6-approximation algorithm for Group GAP instances where the total size of each group is at most m/n. At the heart of our algorithm lies an interesting derivation of a submodular function from the classic LP formulation of GAP, which facilitates the construction of a high profit solution utilizing at most half the total bin capacity, while the other half is reserved for later use. In particular, we give an algorithm for submodular maximization subject to a knapsack constraint, which finds a solution of profit at least 1/3 of the optimum, using at most half the knapsack capacity, under mild restrictions on element sizes. Our novel approach of submodular optimization subject to a knapsack with reserved capacity constraint may find applications in solving other group assignment problems.
AB - We study a variant of the generalized assignment problem (GAP) with group constraints. An instance of Group GAP is a set I of items, partitioned into L groups, and a set of m uniform (unit-sized) bins. Each item i ϵ I has a size si > 0, and a profit pi,j ≥ 0 if packed in bin j. 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 profit from satisfied groups is maximized. We point to central applications of Group GAP in Video-on-Demand services, mobile Device-to-Device network caching and base station cooperation in 5G networks. Our main result is a 1/6-approximation algorithm for Group GAP instances where the total size of each group is at most m/n. At the heart of our algorithm lies an interesting derivation of a submodular function from the classic LP formulation of GAP, which facilitates the construction of a high profit solution utilizing at most half the total bin capacity, while the other half is reserved for later use. In particular, we give an algorithm for submodular maximization subject to a knapsack constraint, which finds a solution of profit at least 1/3 of the optimum, using at most half the knapsack capacity, under mild restrictions on element sizes. Our novel approach of submodular optimization subject to a knapsack with reserved capacity constraint may find applications in solving other group assignment problems.
KW - Approximation algorithms
KW - Group Generalized assignment problem
KW - Knapsack constraints
KW - Submodular maximization
UR - http://www.scopus.com/inward/record.url?scp=85074865426&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85074865426&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ESA.2019.69
DO - 10.4230/LIPIcs.ESA.2019.69
M3 - Conference contribution
AN - SCOPUS:85074865426
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 27th Annual European Symposium on Algorithms, ESA 2019
A2 - Bender, Michael A.
A2 - Svensson, Ola
A2 - Herman, Grzegorz
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 27th Annual European Symposium on Algorithms, ESA 2019
Y2 - 9 September 2019 through 11 September 2019
ER -