Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2018.24
URN: urn:nbn:de:0030-drops-94287
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9428/
Sarpatwar, Kanthi ; Schieber, Baruch ; Shachnai, Hadas
Generalized Assignment of Time-Sensitive Item Groups
| pdf-format: |
|
Abstract
We study the generalized assignment problem with time-sensitive item groups (chi-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 chi_j = [r_j, d_j]subseteq [T] in which it can be packed. Each item i in group j has a size s_i>0 and a non-negative utility u_{it} when packed into bin t in chi_j. 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 Omega(1)-approximation algorithm for chi-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.
BibTeX - Entry
@InProceedings{sarpatwar_et_al:LIPIcs:2018:9428,
author = {Kanthi Sarpatwar and Baruch Schieber and Hadas Shachnai},
title = {{Generalized Assignment of Time-Sensitive Item Groups}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
pages = {24:1--24:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-085-9},
ISSN = {1868-8969},
year = {2018},
volume = {116},
editor = {Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9428},
URN = {urn:nbn:de:0030-drops-94287},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.24},
annote = {Keywords: Approximation Algorithms, Packing and Covering problems, Generalized Assignment problem}
}
| Keywords: | Approximation Algorithms, Packing and Covering problems, Generalized Assignment problem | |
| Seminar: | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 13.08.2018 |
