2026-08-17T19:48:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9428 2024-03-06T10:44:22Z ddc:004 open_access

Generalized Assignment of Time-Sensitive Item Groups Sarpatwar, Kanthi Schieber, Baruch Shachnai, Hadas Approximation Algorithms Packing and Covering problems Generalized Assignment problem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kanthi Sarpatwar and Baruch Schieber and Hadas Shachnai 2018 Is Part Of LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2018.24 urn:nbn:de:0030-drops-94287 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.24 eng https://creativecommons.org/licenses/by/3.0/legalcode