Generalized assignment of time-sensitive item groups

Kanthi Sarpatwar, Baruch Schieber, Hadas Shachnai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018
EditorsEric Blais, Jose D. P. Rolim, David Steurer, Klaus Jansen
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770859
DOIs
StatePublished - Aug 1 2018
Externally publishedYes
Event21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018 - Princeton, United States
Duration: Aug 20 2018Aug 22 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume116
ISSN (Print)1868-8969

Conference

Conference21st International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2018 and the 22nd International Workshop on Randomization and Computation, RANDOM 2018
CountryUnited States
CityPrinceton
Period8/20/188/22/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Approximation Algorithms
  • Generalized Assignment problem
  • Packing and Covering problems

Fingerprint Dive into the research topics of 'Generalized assignment of time-sensitive item groups'. Together they form a unique fingerprint.

Cite this