TY - GEN
T1 - Generalized assignment of time-sensitive item groups
AU - Sarpatwar, Kanthi
AU - Schieber, Baruch
AU - Shachnai, Hadas
N1 - Publisher Copyright:
© 2018 Aditya Bhaskara and Srivatsan Kumar.
PY - 2018/8/1
Y1 - 2018/8/1
N2 - We study the generalized assignment problem with time-sensitive item groups (x-AGAP). It has central applications in advertisement placement on the Internet, and in virtual network embedding in Cloud data centers. We are given a set of items, partitioned into n groups, and a set of T identical bins (or, time-slots). Each group 1 ≤ j ≤ n has a time-window xj = [rj , dj[ ∪ [T] in which it can be packed. Each item i in group j has a size si > 0 and a non-negative utility uit when packed into bin t 2 xj . A bin can accommodate at most one item from each group and the total size of the items in a bin cannot exceed its capacity. The goal is to find a feasible packing of a subset of the items in the bins such that the total utility from groups that are completely packed is maximized. Our main result is an (1)-approximation algorithm for x-AGAP. Our approximation technique relies on a non-trivial rounding of a configuration LP, which can be adapted to other common scenarios of resource allocation in Cloud data centers.
AB - We study the generalized assignment problem with time-sensitive item groups (x-AGAP). It has central applications in advertisement placement on the Internet, and in virtual network embedding in Cloud data centers. We are given a set of items, partitioned into n groups, and a set of T identical bins (or, time-slots). Each group 1 ≤ j ≤ n has a time-window xj = [rj , dj[ ∪ [T] in which it can be packed. Each item i in group j has a size si > 0 and a non-negative utility uit when packed into bin t 2 xj . A bin can accommodate at most one item from each group and the total size of the items in a bin cannot exceed its capacity. The goal is to find a feasible packing of a subset of the items in the bins such that the total utility from groups that are completely packed is maximized. Our main result is an (1)-approximation algorithm for x-AGAP. Our approximation technique relies on a non-trivial rounding of a configuration LP, which can be adapted to other common scenarios of resource allocation in Cloud data centers.
KW - Approximation Algorithms
KW - Generalized Assignment problem
KW - Packing and Covering problems
UR - http://www.scopus.com/inward/record.url?scp=85052436233&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052436233&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2018.24
DO - 10.4230/LIPIcs.APPROX-RANDOM.2018.24
M3 - Conference contribution
AN - SCOPUS:85052436233
SN - 9783959770859
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018
A2 - Blais, Eric
A2 - Rolim, Jose D. P.
A2 - Steurer, David
A2 - Jansen, Klaus
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018
Y2 - 20 August 2018 through 22 August 2018
ER -