DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.54

Online Demand Strip Packing

Authors: Sebastian Bruchhold, Franziska Eberle, Georgios Moneftsis, Malin Rau, and Albert Vesterlund

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

In the Demand Strip Packing problem (DSP), we are given a finite set of tasks, each characterized by a specific duration and energy demand. These tasks need to be scheduled non-preemptively within a given time frame while minimizing the peak demand: the maximum amount of energy consumed by the tasks being executed at any point in time. We are the first to consider the online variant of the problem, where tasks are revealed to an algorithm one by one in a list. Upon arrival, each task must be assigned an irrevocable starting time before the next task in the list is revealed. As usual in online optimization, we evaluate the performance of online algorithms using competitive analysis. We give a strictly 4.263-competitive algorithm for Online DSP, which is stronger than the respective bound of 6.479 for the related problem Online Strip Packing. Additionally, we prove a lower bound of 1.812 on the competitive ratio of any online algorithm for DSP and, thus, clearly separate Online DSP from Online Minimum Peak Appointment Scheduling (MPAS), a special case of Online DSP, for which a strictly 5/3-competitive algorithm is known.

Cite as

Sebastian Bruchhold, Franziska Eberle, Georgios Moneftsis, Malin Rau, and Albert Vesterlund. Online Demand Strip Packing. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 54:1-54:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bruchhold_et_al:LIPIcs.ESA.2026.54,
  author =	{Bruchhold, Sebastian and Eberle, Franziska and Moneftsis, Georgios and Rau, Malin and Vesterlund, Albert},
  title =	{{Online Demand Strip Packing}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{54:1--54:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.54},
  URN =		{urn:nbn:de:0030-drops-271909},
  doi =		{10.4230/LIPIcs.ESA.2026.54},
  annote =	{Keywords: Online Demand Strip Packing, competitive analysis, scheduling, packing}
}

Search Results

Documents authored by Vesterlund, Albert

Online Demand Strip Packing

Abstract

Cite as

Thanks for your feedback!

Could not send message