Search Results

Documents authored by Graafsma, Denise

Document
DOI: 10.4230/LIPIcs.STACS.2026.7
Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms

Authors: Antonios Antoniadis, Denise Graafsma, Ruben Hoeksma, and Maria Vlasiou

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
We study the computational complexity of scheduling jobs on a single speed-scalable processor with the objective of capturing the trade-off between the (weighted) flow time and the energy consumption. This trade-off has been extensively explored in the literature through a number of problem formulations that differ in the specific job characteristics and the precise objective function. Nevertheless, the computational complexity of four important problem variants has remained unresolved and was explicitly identified as an open question in prior work (see [Barcelo et al., 2015]). In this paper, we settle the complexity of these variants. More specifically, we prove that the problem of minimizing the objective of total (weighted) flow time plus energy is NP-hard for the cases of (i) unit-weight jobs with arbitrary sizes, and (ii) arbitrary-weight jobs with unit sizes. These results extend to the objective of minimizing the total (weighted) flow time subject to an energy budget and hold even when the schedule is required to adhere to a given priority ordering. In contrast, we show that when a completion-time ordering is provided, the same problem variants become polynomial-time solvable. The latter result highlights the subtle differences between priority and completion orderings for the problem.
Cite as

Antonios Antoniadis, Denise Graafsma, Ruben Hoeksma, and Maria Vlasiou. Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.STACS.2026.7,
  author =	{Antoniadis, Antonios and Graafsma, Denise and Hoeksma, Ruben and Vlasiou, Maria},
  title =	{{Refining the Complexity Landscape of Speed Scaling: Hardness and Algorithms}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.7},
  URN =		{urn:nbn:de:0030-drops-254967},
  doi =		{10.4230/LIPIcs.STACS.2026.7},
  annote =	{Keywords: energy-efficient algorithms, scheduling, flow-time minimization, linear program, NP-hard, speed scaling}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact