License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.69
URN: urn:nbn:de:0030-drops-111906
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11190/
Kulik, Ariel ;
Sarpatwar, Kanthi ;
Schieber, Baruch ;
Shachnai, Hadas
Generalized Assignment via Submodular Optimization with Reserved Capacity
Abstract
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 in I has a size s_i >0, and a profit p_{i,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/2. 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.
BibTeX - Entry
@InProceedings{kulik_et_al:LIPIcs:2019:11190,
author = {Ariel Kulik and Kanthi Sarpatwar and Baruch Schieber and Hadas Shachnai},
title = {{Generalized Assignment via Submodular Optimization with Reserved Capacity}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {69:1--69:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11190},
URN = {urn:nbn:de:0030-drops-111906},
doi = {10.4230/LIPIcs.ESA.2019.69},
annote = {Keywords: Group Generalized Assignment Problem, Submodular Maximization, Knapsack Constraints, Approximation Algorithms}
}
|
Keywords: |
|
Group Generalized Assignment Problem, Submodular Maximization, Knapsack Constraints, Approximation Algorithms |
|
Collection: |
|
27th Annual European Symposium on Algorithms (ESA 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
06.09.2019 |
