Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Gálvez, Waldo; Grandoni, Fabrizio; Ameli, Afrouz Jabal; Khodamoradi, Kamyar https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-147130
URL:

; ; ;

Approximation Algorithms for Demand Strip Packing

pdf-format:


Abstract

In the Demand Strip Packing problem (DSP), we are given a time interval and a collection of tasks, each characterized by a processing time and a demand for a given resource (such as electricity, computational power, etc.). A feasible solution consists of a schedule of the tasks within the mentioned time interval. Our goal is to minimize the peak resource consumption, i.e. the maximum total demand of tasks executed at any point in time.
It is known that DSP is NP-hard to approximate below a factor 3/2, and standard techniques for related problems imply a (polynomial-time) 2-approximation. Our main result is a (5/3+ε)-approximation algorithm for any constant ε > 0. We also achieve best-possible approximation factors for some relevant special cases.

BibTeX - Entry

@InProceedings{galvez_et_al:LIPIcs.APPROX/RANDOM.2021.20,
  author =	{G\'{a}lvez, Waldo and Grandoni, Fabrizio and Ameli, Afrouz Jabal and Khodamoradi, Kamyar},
  title =	{{Approximation Algorithms for Demand Strip Packing}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
  pages =	{20:1--20:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-207-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{207},
  editor =	{Wootters, Mary and Sanit\`{a}, Laura},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14713},
  URN =		{urn:nbn:de:0030-drops-147130},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2021.20},
  annote =	{Keywords: Strip Packing, Two-Dimensional Packing, Approximation Algorithms}
}

Keywords: Strip Packing, Two-Dimensional Packing, Approximation Algorithms
Seminar: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Issue date: 2021
Date of publication: 15.09.2021


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI